💡문제접근
힙(heap)
자료구조에 대해서 알게 된 문제였다. 힙을 사용하기 위해서는 import heapq
을 명시해줘야 사용이 가능하다.
heappop(heap)
는 heap에서 가장 작은 항목을 pop하고 반환해주는 메소드이다.
heappush(heap, item)
는 item값을 heap에 push해주는 메소드이다.
파이썬에서는 최대 힙을 제공하지 않는데 최소 힙을 변형해서 최대 힙을 구현할 수 있다. heappush(heap, item)
부분을 heappush(heap, -item)
으로 부호를 변경해서 push한 다음 heappop(heap)
를 heappop(-heap)
으로 부호를 변경해서 pop하면 된다.
💡코드(메모리 : 37000KB, 시간 : 124ms)
import sys
import heapq
input = sys.stdin.readline
heap = []
N = int(input().strip())
for i in range(N):
num = int(input().strip())
if num != 0:
heapq.heappush(heap, num)
else:
if len(heap) == 0:
print(0)
else:
print(heapq.heappop(heap))
💡소요시간 : 7m