BOJ 11286 - 절댓값 힙

BOJ 11286 - 절댓값 힙

“우선순위 큐”

BOJ 11286 - 절댓값 힙

문제 링크


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int N;

class compare {
    public:
        bool operator() (int a, int b) {
            if (abs(a) != abs(b)) 
                return abs(a) > abs(b);
            return a > 0 && b < 0;  
        }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    priority_queue<int, vector<int>, compare> pq;
    for (int i = 0; i < N; i++) {
        int num; cin >> num;
        if (num == 0) {
            if (pq.empty())
                cout << "0\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else
            pq.push(num);
    }
    return 0;
}

  • STL priority queue에 대해 알고 있다면, 비교 함수를 만들 줄만 안다면 편리하게 풀어낼 수 있는 문제이다. 다만 비교 함수를 만들 때 위치 선정에 헷갈리는 구석이 있었다. 예를 들어 입력이 18 1 -1 0 0로 주어질 경우 나는 1 -1이 출력되어야 한다고 생각했는데 결과는 반대였다. compare 클래스 operator() (int a int b)의 작동 방식에 대해 그림을 그리며 생각해보았다.

  • 우선순위 큐를 상상할 때, 머릿속으로 트리를 그리지만 priority_queue<int, vector<int>, compare>를 보면 알 수 있듯이 벡터로 구현되는 것을 확인할 수 있다. 맨 처음에 1을 push하는 경우 vector<int>에 1을 push할 것이다. 이후 벡터에 -1을 push할 때 operator() (int a int b) 함수가 작동한다. 이때 새로 push되는 -1이 int a, 기존에 존재하던 1이 int b가 된다. 둘의 절댓값이 같기 때문에 return a > 0 && b < 0, 즉 a가 양수이고 b가 음수인 경우에 true를 반환한다.


  • 그런데 벡터를 보면 조건에 위배되어 false가 반환되고, 순서가 바뀌어 -1이 top인 벡터가 완성된다.


  • 1 다음에 2를 넣는다고 생각해도, int a는 2, int b는 1로 절댓값이 다를 때 호출되는
if (abs(a) != abs(b)) 
    return abs(a) > abs(b);
  • 함수에 대하여, a가 2고 b가 1이기 때문에 true고 1이 top인 상태를 유지하게 된다. 만약 false가 반환된다면 절댓값이 작은 쪽에 우선순위에 따라 root에 근접하게 될 것이다.