코드

import heapq

n = int(input())

heap = []

for _ in range(n):
    x = int(input())
    
    if x == 0:
        if not heap:
            print(0)
        else:
            print(-heap[0])
            heapq.heappop(heap)
    else:
        heapq.heappush(heap, -x)

문제 해설

최대 힙을 구하는 문제이다. 파이썬의 heapq는 최소 힙으로 기본 구현되어 있는데 이를 최대 힙으로 구현하려면 heappush() 메소드에 값을 넣을 때, 음수로 넣어주고 출력할 때 다시 그 부호를 바꿔주면 최대 힙의 효과를 가질 수 있다.

heapq에 대한 설명은 최소 힙 문제에서 다루었으므로 링크로 대신한다.

최소 힙 문제 링크

댓글남기기

참고