[백준/1927] 최소 힙

문제를 잘 이해하면 구현은 어렵지 않다.

 

첫번째 시도

import sys
n = int(sys.stdin.readline())
heap = []
# 자연수라면 in heap 0이라면 출력 + out heap

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

    if x == 0 and len(heap) != 0:
        print(min(heap))
        heap.remove(min(heap))
    elif x != 0:
        heap.append(x)
    else:
        print(0)

 

혼자서 문제에 따라 잘 구현한 것같은데,, 시간 초과ㅠㅠ

구글링 후 알게된 점은 파이썬에서 따로 heappush, heappop을 제공한다는 것이었다..! (from heapp 모듈)

 

 

파이썬 heapq 모듈 

대표적인 메소드 : heappush, heappop

• heappush(heap, x) : x 값을 힙으로 push한다. 이때 heap은 리스트 형식으로 구현하는 경우가 많다.
• heappop(heap) : 힙에서 가장 작은 항목을 pop, 반환한다.

 

최종 코드

---

import sys
import heapq

n = int(sys.stdin.readline())
H = []
# 자연수라면 in heap 0이라면 출력 + out heap

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

    if x!=0:
        heapq.heappush(H, x) # H에 x push
        
    elif x == 0 and len(H) != 0:
        print(heapq.heappop(H))
        
    else:
        print(0)

 

list H와 heapq 모듈을 활용해서 코드를 구현했다.

처음에는 if문 순서 문제인가 싶어서 이리저리 코드를 바꿔보았는데 결국엔 모듈로 해결,,,