[백준] 11286번 : 절댓값 힙

문제

 

---

풀이

 

myunji.tistory.com/271

[백준] 11279번 : 최대 힙

myunji.tistory.com/272

[백준] 1927번 : 최소 힙

앞서 최대 힙과 최소 힙을 구현했다.

우선순위 큐 함수의 3번째 인자를 greater로 설정해서 최소 힙을 구현했는데...

sort 함수에서 내맘대로 정렬기준을 설정할 수 있었던 것처럼 우선순위 큐에서도 그렇게 할 수 있다.

---

소스코드

 

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct cmp {
    bool operator()(int a, int b) { //a가 부모 노드, b가 자식 노드 일 때. true 반환하면 swap
        if (abs(a) == abs(b))
            return a > b;
        return abs(a) > abs(b);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    priority_queue<int, vector<int>, cmp> pq;
    int N, x;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x;
        if (x == 0) {
            if (pq.empty())
                cout << 0 << '\n';
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        } else
            pq.push(x);
    }
}

여기서 주목할 것은 cmp 구조체 뿐이다.

 

struct cmp {
    bool operator()(int a, int b) { //a가 부모 노드, b가 자식 노드 일 때. true 반환하면 swap
        if (abs(a) == abs(b))
            return a > b;
        return abs(a) > abs(b);
    }
};

두 인자 a(부모 노드)와 b(자식 노드)가 있을 때, operator 함수가 true를 반환하면 b가 부모 노드로 올라가게 된다.

 

이 문제에서 b가 a보다 앞에 있을 경우는

1. b의 절댓값이 a의 절댓값보다 작음.

2. 두 인자의 절댓값이 같다면 a보다 b가 작음.

이다.