백준 1927 최소 힙

문제

최소 힙

최소 힙을 이용해 heappush, heappop 연산

난이도 : Silver2

---

풀이

1. 주어진 값들을 최소 힙에 하나씩 넣는다.
2. 빈 힙이 아니라면 최솟값을 출력하고 pop 한다.

---

코드

import sys
import heapq

N = int(sys.stdin.readline())
x = [int(sys.stdin.readline()) for _ in range(N)]
new = []  # 최소 힙

for i in range(N):
    if x[i] == 0:
        if not new:  # 배열이 비어있으면 0 출력
            print(0)
        else:
            print(heapq.heappop(new))  # 가장 작은 값 삭제 후 출력
    else:
        heapq.heappush(new, x[i])  # heappush로 새로운 값 추가
   

---

결과

처음엔 heapify를 매 반복마다 해주니 시간 초과가 떴다. heap에 대한 더 깊은 이해가 필요한 듯 하다.