[백준/C++] 11279번: 최대 힙

문제&링크

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

 

풀이

1. 우선순위 큐를 이용하여 최대 힙을 만든다.

2. 0을 입력받은 순간 최대 힙이 비어있다면 0을 출력한다.

3. 0을 입력받은 순간 최대 힙이 비어있지 않다면 제일 큰 값, 즉 우선 순위 큐의 top에 해당하는 값을 출력한다.

4. 0이 아닌 다른 수를 입력받을 경우 최대 힙에 저장한다.

 

코드

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> pq;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        
        if (num == 0) {
            if (pq.empty()) cout << 0 << "\n";
            else {
                cout << pq.top() << "\n";
                pq.pop();
            }
        }
        else {
            pq.push(num);
        }
        
    }
}