99클럽 코테 스터디 19일차 TIL + 힙(C++)

문제

[백준] 1927번: 최소 힙

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

 

코드

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

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

    int N;
    cin >> N;

    // 우선순위 큐 생성 - 내림차순 정렬(최소 힙)
    priority_queue<int, vector<int>, greater<int>> pq;

    while (N--) {
        int x;
        cin >> x;

        if (x > 0)
            pq.push(x);
        if (x == 0) {
            if (pq.empty()) {
                cout << 0 << '\n';
                continue;
            }
            cout << pq.top() << '\n';
            pq.pop();
        }
    }

    return 0;
}

 

풀이

우선순위 큐(Priority Queue)를 사용해 최소 힙을 구현하는 문제.

 

!주의할 점!

C++에서 queue STL을 사용해 우선순위 큐 생성시, 기본적으로 큐 안의 요소들이 내림차순으로 정렬된다. 즉, 최대 힙으로 구현된다.

문제에서는 최소 힙을 구현해야 하므로, 우선순위 큐 생성시 세번째 매개변수에 greater<int>를 전달해 큐 안의 원소들을 내림차순으로 정렬해주어야 한다.

 

우선순위 큐 설명 참고)

https://breakcoding.tistory.com/123

[C++] <queue> 라이브러리, 우선순위 큐, 최대 힙, 최소 힙