[Python] 백준/BOJ 1927번: 최소 힙 (Silver 2)

💻 Problem

문제 보러 가기

 

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

💡 Approach

heapq 모듈 활용하여 최소 힙을 구현했다.

 

✏️ Solution

import sys
import heapq
input = sys.stdin.readline

n = int(input())
heap = []

for _ in range(n):
    x = int(input())

    if x == 0:
        print(heapq.heappop(heap) if heap else 0)
    else:
        heapq.heappush(heap, x)

힙에서 삽입이나 삭제는 log n만큼 걸린다.

이를 n번 실행하니 시간복잡도는 n log n이다.