[알고리즘] 백준 1927 : 최소 힙 - S2

2023.04.27 풀이

import sys
input=sys.stdin.readline
import heapq

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

for i in range(n):
    x=int(input())
    if x==0 and len(heap)==0:
        print(0)
    elif x==0:
        print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, x)

다른 풀이

import sys
import heapq

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

#Max Heap
for _ in range(numbers):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, num)
    else:
        try:
            print(heapq.heappop(heap))
        except:
            print(0)

import sys
import heapq

N = int(sys.stdin.readline())
heap = []
for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print('0')
    else:
        heapq.heappush(heap, x)

check point

힙

• 푸쉬 : heapq.heappush(heap, item)
• 팝 : heapq.heappop(heap)
  가장 작은 원소를 pop&리턴. 비어있는경우-IndexError
  
  
• heapq 모듈 :이진 트리(binary tree) 기반의 최소 힙
  원소들이 항상 정렬된 상태로 추가/삭제되며,
  가장 작은값은 언제나 인덱스 0(이진 트리의 루)트에 위치
  내부적으로 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소 추가/삭제 됨.