[파이썬/python] 백준 1927 - 최소 힙

문제

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

---

문제 설명

1.   최소 힙 구조를 이용하여 아래 연산을 지원하는 프로그램을 작성한다.
   1. 배열에 자연수 x를 넣는다.
   2. 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거한다.

 

---

풀이

파이썬의 heapq 라이브러리를 이용한다.

1. 수를 입력받는다.
   1. 입력받은 수가 0일 때
      1. heap 배열의 크기가 0이라면 0을 출력한다.
      2. heap 배열의 크기가 1 이상이라면 가장 작은 수를 출력한다.
   2. 입력받은 수가 0이 아닌 수일 때
      1. heap 배열에 수를 저장한다.

---

코드

import sys
import heapq
input = sys.stdin.readline

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

for i in range(N):
    temp = int(input())
    if temp == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap,temp)

---

시간복잡도

• 우선순위큐(heap)의 삽입, 삭제 시간 복잡도는 $O(logN)$이다.
• 총 N회 반복하므로 $O(NlogN)$
• 최악일 경우N = $10^5$이므로, $O(10^6)$의 시간복잡도를 가지게된다.