1927 - 최소 힙 (silver 2)

"""
1927 - 최소 힙 (silver 2)
"""
import sys

input = sys.stdin.readline

arr = []
n = int(input().rstrip())
for i in range(n):
    x = int(input().rstrip())
    if x == 0:
        if not arr:
            print("0")
        else:
            pop_index = arr.index(min(arr))
            print(arr.pop(pop_index))
    else:
        arr.append(x)

- 시간 초과

 

"""
1927 - 최소 힙 (silver 2)
"""
import sys
from collections import deque

input = sys.stdin.readline

arr = deque([0])
n = int(input().rstrip())

for i in range(n):
    x = int(input().rstrip())
    if x == 0:
        if len(arr) == 1:
            print(arr[0])
        else:
            arr.popleft()
            arr.popleft()
            arr.appendleft(arr.pop())
            arr.appendleft(0)
            node = 1
            while True:
                lchild, rchild = node * 2, node * 2 + 1
                compare_lchild = arr[node] - arr[lchild]
                compare_rchild = arr[node] - arr[rchild]
                if compare_lchild > 0 or compare_rchild > 0:
                    if compare_lchild > compare_rchild:
                        temp = arr[node]
                        arr[node] = arr[lchild]
                        arr[lchild] = temp
                        node = lchild
                    else:
                        temp = arr[node]
                        arr[node] = arr[rchild]
                        arr[rchild] = temp
                        node = rchild
                else:
                    break
    else:
        arr.append(x)
        node = len(arr) - 1
        while True:
            parent = node // 2
            if arr[node] < arr[parent]:
                temp = arr[node]
                arr[node] = arr[parent]
                arr[parent] = temp
                node = parent
            else:
                break
print(arr)

- 최소 힙 검색 후, 내가 짠 코드 / 에러 발생 (IndexError: deque index out of range) 

 

"""
1927 - 최소 힙 (silver 2)
"""
import sys
import heapq

input = sys.stdin.readline

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

for _ in range(n):
    x = int(input().rstrip())
    if x != 0:
        heapq.heappush(heap, x)
    else:
        try:
            print(heapq.heappop(heap))
        except:
            print(0)

우선순위 큐(최소 힙) 알고리즘

- 파이썬의 heapq 모듈로 힙 자료구조 사용하기

(https://www.daleseo.com/python-heapq/)

- heapq 모듈 사용 기본 문제