solved.ac CLASS 3 11286 절대값 힙

문제링크 : https://www.acmicpc.net/problem/11286

 

1. 입력 관련

 

힙과 관련된 문제였다. 힙을 직접 구현하지 않고 힙의 구조를 가지고 있는 priority queue 를 사용했다.

 

절대값이 가장 작다는 것은 0과 가장 가깝다는 것이다. 즉 -1 과 3 을 비교 했을 때 -1 이 더 가깝다는 것이다.

즉 가장 0과 가까운 수를 결정할 때 부호는 영향을 주지 않는다. 하지만 출력을 할 때는 부호를 신경써야 하기 떄문에 아래와 같은 pair 를 둔다.

 

pair<수, 부호> 

 

소스는 아래와 같다.

#include <iostream>
#include <queue>

using namespace std;

int N, inp;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pair<int, int> pqTop;

int main(void){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> inp;
        if(inp < 0) pq.push(make_pair(-inp, -1));
        else if(inp > 0) pq.push(make_pair(inp, 1));
        else {
            if(pq.empty()) cout << 0 << '\n'; // pq 가 비었는데 pop 요청이 들어올 경우 0 출력
            else{
                cout << pq.top().first * pq.top().second << '\n';
                pq.pop();
            }
        }
    }
    
    return 0;
}