[C++] 백준 1927. 최소 힙

문제 설명

자연수가 입력되면 배열에 추가하고, 0이 입력되면 가장 작은 수를 출력하고 배열에서 제거한다.

배열이 비어 있을 때 0이 입력되면 0을 출력한다.

문제 접근

문제에서도 최소 힙을 사용하라고 되어 있고, 최소 힙은 가장 작은 수가 root에 있도록 정렬되기 때문에 문제에서 요구하는대로 배열이 구성된다. C++에서는 STL인 우선순위 큐를 이용하면 된다.

priority_queue는 기본적으로 최대 힙이기 때문에, 옵션을 주어 최소 힙으로 동작하게 수정한다.

 

전체 코드

#include <iostream>
#include <queue>

using namespace std;

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

    int N, x;
    priority_queue<int, vector<int>, greater<>> minHeap; // 최소 힙

    cin >> N;

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

        if (x > 0) {
            minHeap.push(x); // x가 양수일 경우 최소 힙에 추가
        } else { // x가 0인 경우
            if (minHeap.empty()) {
                cout << 0 << "\n"; // 힙이 비었으면 0 출력
            } else {
                cout << minHeap.top() << "\n"; // 가장 작은 값 출력
                minHeap.pop(); // 출력한 값 제거
            }
        }
    }

    return 0;
}