[백준 / Python] 1927번 최소 힙

문제

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

1927번: 최소 힙

 

---

소스코드

import heapq
import sys
# 최소힙 문제 
# heapq.heappush(heap, item) : item을 heap에 추가
# heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
# heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 
N = int(input())
ls = []

for i in range(N):
    
    a = int(sys.stdin.readline())
    if a == 0:
        if ls:
        	print( heapq.heappop(ls))
            
        else:
            print(0)
            
    else:
        heapq.heappush(ls, a)

 

우선순위 큐 문제입니다.

힙큐 알고리즘이 구현되어있는 파이썬의 heapq를 사용한다면 쉽게 풀 수 있습니다. 

 

힙큐의 시간 복잡도는 삽입, 삭제가 O(logN)을 가집니다.