백준 | 최대 힙

백준 최대 힙

파이썬의 heapq 모듈을 활용했는데, 이는 기본적으로 최소 힙(min heap)으로 작동한다. 따라서 자연수 x를 저장할 때, -x를 저장하여 heappop()의 결과로 최댓값이 출력되도록 했다.

예를 들어, x가 차례대로 5, 3, 8이 주어졌다고 할 때, 그대로 저장하면 heappop()의 결과는 3이 된다. 반면 -x 형태로 저장하면 -5, -3, -8이 저장되고, heappop()의 결과는 -8이고, 다시 -를 붙여 출력하면 실제 최댓값인 8이 출력된다.

import sys
import heapq


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

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

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

힙(heap) 개념은 아래 블로그를 참고했다.

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html