백준 1927 최소 힙

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

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>> q;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;

        cin >> x;

        if (x == 0) {
            if (!q.empty()) {
                cout << q.top() << "\n";
                q.pop();
            } else {
                cout << 0 << "\n";
            }
        } else {
            q.push(x);
        }

    }


    return 0;
}

1. 문제

최소 힙에 대한 n개의 연산이 주어진다. 자연수가 들어갈 경우 배열에 그 값을 추가하고, 0이 입력될 경우 해당 배열의 최솟값을 출력 후 이를 제거한다. 연산의 결과를 출력하는데, 배열이 비어있을 때 0이 입력될 경우 0을 출력한다.

2. 풀이

priority_queue<int, vector<int>, greater<int>> q;

 

위와 같이 우선순위 큐를 정의한다. greater<int>로 top에 최솟값을 놓을 수 있다.

        cin >> x;

        if (x == 0) {
            if (!q.empty()) {
                cout << q.top() << "\n";
                q.pop();
            } else {
                cout << 0 << "\n";
            }
        } else {
            q.push(x);
        }

n개 만큼 수를 입력받고, 0일 경우 최솟값인 top을 출력 후 이를 제거한다. 자연수일 경우 x를 우선순위 큐에 push한다. 이를 반복하면 정답을 구할 수 있다.