[BOJ] #11286 절댓값 힙

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

11286번: 절댓값 힙

---

우선순위 큐에 관련된 간단한 예제이다. 입력되는 인덱스들의 절댓값이 더 작은 원소들을 출력하고, 절댓값이 같다면 실제 인덱스 값이 더 작은 (쉽게 말해 양수와 음수중 음수를 출력) 값을 출력하면 된다.

이 매커니즘을 구현하려면 먼저 우선순위 큐 라는 자료구조를 알고 있어야 한다. 우선순위 큐에 대한 내용은 다음 게시글에서 자세하게 작성해 놓았다.

https://jhoon-study.tistory.com/75

[C++] STL priority_queue 사용법

이 문제에서 키 포인트는, 절댓값이 같은 원소들에 대해 음수를 먼저 출력해야 한다는 것인데, 그냥 우선순위 큐에 저장할때에 절댓값과 실제 인덱스를 pair형으로 같이 저장하는 방법으로 해결하였다. 따라서, 우선순위 큐를 선언하는 구문은 다음과 같다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

우선순위 큐의 기본 설정인 내림차순 정렬 또한 바꿔주고자 greater<pair<int,int>>도 같이 달아주었다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int N;
    cin >> N;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    while (N-->0) {
        int a;
        cin >> a;

        if (a==0) {
            if (pq.empty()) cout << 0 << '\n';
            else {
                cout << pq.top().second << '\n';
                pq.pop();
            } 
        }
        else {
            pq.push(make_pair(abs(a), a));
        }
    }

    return 0;
}