greentea31's Note

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

풀이 과정

최소 힙을 이용하여 문제에서 주어진 연산을 지원하는 프로그램을 작성하면 된다.

힙은 이진트리의 일종이므로 일차원 배열로 직접 구현이 가능하나, 라이브러리에 구현되어 있는 힙을 사용하였다.

C++의 경우에는 기본이 최대 힙이고, 파이썬은 기본이 최소 힙이다.

priority_queue<int> max_heap; // 최대 힙
priority_queue<int, vector<int>, greater<int>> min_heap; // 최소 힙

import heapq

heap = []
heapq.heappush(3)
heapq.heappush(5) # 기본은 최소힙

max_heap = []
heapq.heappush((-3, 3))
heapq.heappush((-5, 5)) # 이런 테크닉을 이용하여 최소힙을 최대힙처럼 사용해야 한다

소스 코드

c++

#include <bits/stdc++.h>
using namespace std;

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

    priority_queue<int, vector<int>, greater<int>> pq;
    int N, num;
    cin >> N;
    while (N--) {
        cin >> num;
        if (num == 0) {
            if (pq.empty()) {
                cout << 0 << '\n';
            } else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        } else {
            pq.push(num);
        }
    }

    return 0;
}

Python

import heapq
import sys

heap = []
N = int(sys.stdin.readline())

for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
        continue
    heapq.heappush(heap, x)