(C++) 백준 11286번 - 절대값 힙

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

11286번: 절댓값 힙

풀이

우선순위 큐와 커스텀 비교 함수를 사용하여 풀이하였다.

우선순위 큐에서는 가장 뒤에 위치한 값이 가장 우선순위가 높다는 것이 풀이하면서 상당히 헷갈리게 만들었다.

또한 우선순위 큐에서 비교 함수를 사용하기 위해서 아래와 같이 cmp라는 클래스와 내부의 operator()를 사용해야 한다는 사실도 새롭게 알게 되었다.

#include <iostream>
#include <queue>

using namespace std;

class cmp{
public:
    bool operator() (int a, int b){
        if(abs(a) != abs(b)) return abs(a) > abs(b);
        else return a > b;
    }
};

int n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priority_queue<int, vector<int>, cmp> q;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        if(x == 0){
            if(q.empty()) cout << 0 << "\n";
            else{
                cout << q.top() << "\n";
                q.pop();
            }
        }
        else q.push(x);
    }
}