[BOJ/C++] 최소 힙(1927번)

1. 개요

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

1927번: 최소 힙

1-1. 설명

최소힙을 이용해 다음과 같은 연산을 지원하는 프로그램을 작성한다

 - 배열에 자연수 x를 넣음

 - 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거
프로그램은 처음에 비어있는 배열에서 시작하게 된다. 

1-2. 제한 사항

 - 첫줄에 연산의 개수 N이 주어지며, N은 1 이상 100,000 이하

 - 다음 N개 줄에 연산에 대한 정보를 나타내는 정수 x가 주어짐

 - x가 자연수이면 배열에 x를 추가하는 연산이고, 0이라면 배열에서 가장 작은값 출력 후 제거

 - x는 2^31보다 작은 자연수 or 0

---

2.구현

2-1. 풀이

우선순위 큐 STL을 통해 간단하게 구현하였다.

2-2. 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, num;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> queue;
    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num == 0 && queue.size() == 0) {
            cout << "0\n";
            continue;
        }
        else if (num == 0) {
            cout << queue.top() << "\n";
            queue.pop();
        }
        else queue.push(num);
    }

    return 0;
}