[BOJ/C++] 최대 힙(11279번)

1. 개요

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

11279번: 최대 힙

1-1. 설명

널리 알려진 자료구조 중 최대 힙이 존재한다. 최대 힙을 이용해 다음과 같은 연산을 지원하는 프로그램을 작성한다. 

 - 배열에 자연수 x를 넣음

 - 배열에서 가장 큰 값 출력, 그 값 제거

프로그램은 처음 비어있는 배열에서 시작한다. 

1-2. 제한 사항

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

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

 - x가 자연수일 때 배열에 추가하고 0이라면 배열에서 가장 큰값을 출력하고 제거한다. 

---

2. 구현

2-1. 풀이

정말 단순하게 우선순위 큐로 풀었다. 

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;
    priority_queue<int> queue;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num != 0) queue.push(num);
        else {
            if (!queue.empty()) {
                cout << queue.top() << "\n";
                queue.pop();
            }
            else cout << "0\n";
        }
    }
    return 0;
}