[백준 파이썬] # 1927 최소 힙

Silver II

# 1927 최소 힙

링크 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

풀이

import heapq
import sys

heap = []
N = int(sys.stdin.readline())
for i in range(N):
    num = int(sys.stdin.readline())
    if num == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, num)

 

후기

• 힙이라는 자료구조에 대해 배우고 나서 풀 수 있었다.
  
  
• 파이썬에서는 heapq 모듈을 사용해서 힙 자료구조를 사용할 수 있으며, 일반적으로 최소 힙(min heap)을 구현할 수 있다
  
  
• 리스트를 기반으로 힙을 이용한다
  
  
• 힙에 요소 추가 : heapq.heappush(리스트, 추가 요소)
  힙의 요소 제거 : heapq.heappop(리스트, 제거 요소) - 가장 작은 값이 제거된다
  기존 리스트를 리스트 힙으로 만들기 : heapq.heapify(리스트)
  
  
• 힙에 대해서 잘 정리된 자료를 참고해보자
  
  

heap 모듈 사용법

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

 

자료구조 설명(by 나동빈님)

https://www.youtube.com/watch?v=AjFlp951nz0

 

 

 

https://www.youtube.com/watch?v=iyl9bfp_8ag&t=992s