https://www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
import heapq
import sys
input = sys.stdin.readline ## 시간초과 방지
N = int(input())
heap = []
for _ in range(N):
x = int(input())
if x == 0:
if not heap:
print(0)
else:
print(heapq.heappop(heap))
else:
heapq.heappush(heap, x)이 문제는 힙 정렬과 무척 관련이 있는 문제이다.
우선 heap은 https://junheelab.tistory.com/140의 세그먼트 트리와 같이 루트노드가 있고 그 자식들은 항상 n * 2 +1과 n * 2 + 2의 인덱스를 갖는다.
만약 이를 직접 구현하려면 무척 복잡하지만 파이썬에는 친절하게도 heapq라는 모듈이 있어 이를 쉽게 구현할 수가 있다.
자세한 heapq모듈 사용법은 이쪽 블로그를 참고하면 좋겠고 자료구조의 우선순위 큐를 알고싶다면 동빈나 님의 유튜브를 참조하는 것이 바람직하다. 나는 둘 모두 참조했다.