[백준/Python] 1927번. 최소 힙

문제

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

 

 

 

풀이

제목 그대로 최소 힙 자료구조를 사용하는 문제이다.

최소 힙은 부모 노드가 자식 노드보다 작은 값을 가지는 완전 이진 트리로 구현된 자료구조이고

따라서 최소힙의 Root 노드에는 항상 전체 트리의 최솟값이 저장된다.

 

파이썬은 편리하게도 heapq 모듈을 import하면 최소 힙 자료구조를 사용할 수 있다.

 

힙으로 사용할 빈 리스트를 선언하고 
heapq.heappush(리스트, 값)으로 값을 push하고
heapq.heappop(리스트)로 Root노드의 최소 값을 pop하다. 간단하다.

 

heapq 모듈은 최대 힙의 구현은 없지만 최소 힙을 이용해 최대 힙도 구현할 수 있다.

 

 

 

 

정답 코드

import heapq
import sys
input = sys.stdin.readline

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