[BOJ/백준] 11286번. 절댓값 힙 - C++[cpp]

https://www.acmicpc.net/problem/11286

 

 

 

힙을 이용하여 문제를 해결해야 하기 때문에 C++에서 제공하는 priority_queue를 사용할 수 있다.

절대값을 기준으로 비교하기 때문에 함수 객체를 만들고, 우선순위 큐의 comparator로 사용하여 문제를 해결하면 된다.

 

comparator의 구체적인 작동방식이 헷갈려서 우선순위 큐에서 비교자의 작동 방식에 대해 적어보겠다.

 

비교자의 작동 방식

비교자의 작동 방식을 더 구체적으로 이해해봅시다.

여기서 간주한다는 의미는, 우선순위가 낮다는 의미이다.

• std::less는 x < y가 true일 때 x가 y보다 작다고 간주합니다. 최대 힙에서 이는 큰 값이 높은 우선순위를 가지게 만듭니다.
  • x가 y보다 작을 때, 작다고 간주하는게 당연하다고 생각할 수 있다. 하지만 std::greater는 x가 y보다 클 때 x가 y보다 작다고 간주한다.
  • x값이 y값보다 작을 때 x의 우선순위가 낮다는 의미이다. 값이 작은게 우선순위가 낮다 --> 큰 값이 우선순위가 높다 --> 최대 힙
• std::greater는 x > y가 true일 때 x가 y보다 작다고 간주합니다. 최소 힙에서 이는 작은 값이 높은 우선순위를 가지게 만듭니다.
  
  • x값이 y값보다 클 때 x의 우선순위가 낮다는 의미이다. 값이 큰 게 우선순위가 낮다 --> 작은 값이 우선순위가 높다 --> 최소 힙

따라서, std::less를 사용하면 큰 값이 우선순위를 가지게 되어 최대 힙이 되고, std::greater를 사용하면 작은 값이 우선순위를 가지게 되어 최소 힙이 됩니다.

 

이 원리를 이해하고 함수 객체를 만들어 문제를 해결해보자. 

 

Code

함수 객체를 따로 만들긴 귀찮아서 람다 함수를 이용했다.

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    auto compare = [](int a, int b) { 
        if (abs(a) == abs(b))
			return a > b;
		else
			return abs(a) > abs(b);
    };
    priority_queue<int, std::vector<int>, decltype(compare)> absHeap(compare);
    cin >> n;
    while (n--) {
        cin >> x;
        if (x != 0) {
            absHeap.push(x);
        }
        else {
            if (absHeap.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << absHeap.top() << '\n';
                absHeap.pop();
            }
        }
    }
}