백준 | 최소 힙

최소 힙 문제

최소 힙(Min Heap)이라는 자료 구조를 이용하여, 아래의 두 연산을 지원하는 프로그램을 만들어야 한다.

[1] 배열에 자연수 x(231보다 작은 자연수 또는 0)를 넣는다.
[2] 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

이때 x가 자연수면 배열에 x를 추가하고, x가 0이면 배열에서 가장 작은 값을 출력하고 배열에서 그 값을 제거해야 한다.

파이썬의 heapq 라이브러리를 사용하여 문제를 해결할 수 있다.

코드(정답)는 다음과 같다.

import sys
import heapq


n = int(sys.stdin.readline())

min_heap = []
for _ in range(n):
    x = int(sys.stdin.readline())

    if x == 0:
        if min_heap:
            print(heapq.heappop(min_heap))
        else:
            print(0)
    else:
        heapq.heappush(min_heap, x)