1927. 최소 힙

1927 문제 보기

접근 방식

제목부터 최소 힙이었어서 파이썬의 모듈 heapq를 사용해 구현하면 되겠다고 생각했다. 쉽게 푼 문제!

heapq 정리하고 가기

• heapq.heappush(heap, item) : item을 heap에 추가하는 함수
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하는 함수.
  • 비어 있는 경우 IndexError가 호출됨.
• heapq.heapify(x) : 리스트 x를 heap으로 변환하는 함수
  • $O(N)$ 소요

최대 힙, 최소 힙 만들기

파이썬의 heapq 기본 값 : 최소 힙

• 최대 힙으로 만드려면? heapq에 넣는 원소를 (-item, item) 형식으로 튜플 형태로 넣어줄 것
  • 튜플의 첫번째 원소를 우선순위로 힙 구성

heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

우선순위 큐

우선순위 큐의 경우 코딩테스트에서 사용할 일은 크게 없을 것 같다..!!
잘 정리되어 있는 링크가 있으니 한 번 보고 들어가기!

https://www.daleseo.com/python-priority-queue/

최종 코드

# 1927 최소 힙
# 시작 시간 - 10:10
# 1차 풀이 종료 시간 - 10:24(정답)
# ---------------------------------------------
# < 1차 접근 >
# 최소 힙 사용
import sys
import heapq
input = sys.stdin.readline

N = int(input().rstrip())
hq = []
for _ in range(N):
  cmd = int(input().rstrip())
  if cmd == 0:
    if hq:
      print(heapq.heappop(hq))
    else:
      print(0)
  else:
    heapq.heappush(hq, cmd)