[BOJ] #1926 - 최소 힙

se0m 2021. 6. 18. 16:08

1927번: 최소 힙

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

www.acmicpc.net

** 문제 유형

힙, 자료구조

** 풀이

파이썬에서 heapq 라이브러리를 이용하면 간단히 힙 구현 가능

import heapq

n = int(input())

heap = []
result = []

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

    if data == 0:
        if heap:
            result.append(heapq.heappop(heap))
        else: # 힙이 비어있는 경우
            result.append(0)
    else:
        heapq.heappush(heap, data)

for data in result:
    print(data)

저작자표시 비영리 변경금지 (새창열림)