코딩테스트/백준

[Python] 백준 1927. 최소힙

jungmin.park 2023. 11. 21. 09:40

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

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

풀이 설계:

  • 입력받은 값이 0이고
    • 힙이 비어있으면 0을 출력한다.
    • 힙이 비어있지 않으면 값을 꺼낸다.
  • 입력받은 값이 0이 아니면 힙에 값을 추가한다.

 

import sys
import heapq

input = sys.stdin.readline
n = int(input())
heap = []

for case in range(n):
    num = int(input())
    if num == 0:
    	#입력받은 값이 0이고
		#힙이 비어있으면 0을 출력한다.
        if len(heap) == 0:
            print(0)
        # 힙이 비어있지 않으면 값을 꺼낸다.
        else:
            print(heapq.heappop(heap))
	# 입력받은 값이 0이 아니면 힙에 값을 추가한다.
    else:
        heapq.heappush(heap, num)