문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1
9
0
12345678
1
2
0
0
0
0
32
예제 출력 1
0
1
2
12345678
0
heapq 모듈은 Python에서 힙 자료구조를 제공하며, 기본적으로 최소 힙(Min Heap)을 지원합니다.
최소 힙의 성질: 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같습니다.
이는 힙의 루트 노드가 최솟값을 가지게 하며, 트리 전체에서 최솟값에 빠르게 접근할 수 있게 합니다.
import sys
import heapq #heapq 모듈을 사용하기 위해 불러오기
N = int(sys.stdin.readline()) # 한번에 입력을 받아오므로, 시간초과 방지
heap = [] # heap을 저장하기 위한 리스트 / 초기화
for _ in range(N): # 입력으로 주어진 개수 'N' 만큼 반복
x = int(sys.stdin.readline()) # 입력으로 들어오는 정수값 받기
if x == 0 : # 입력값이 0인 경우
if heap: # heap이 비어있지 않으면
print(heapq.heappop(heap)) # 힙에서 최소값을 꺼내어 출력
else: # 힙이 비어있을 경우 '0'을 출력
print('0')
else: # 받은 값이 0이 아닌 경우,
heapq.heappush(heap,x) # 'x'를 힙에 추가한다. ( 최소 힙으로 유지된다 )
heapq 모듈의 특징과 성능
-
자동 정렬: heapq 모듈은 요소를 추가할 때마다 자동으로 최소 힙의 성질을 유지합니다. 즉, 요소를 추가하거나 제거할 때마다 최상의 성능을 제공합니다.
-
시간 복잡도: heapq.heappop(heap) 및 heapq.heappush(heap, x)는 각각 O(log N)의 시간 복잡도를 가집니다. 따라서 힙에 새로운 요소를 추가하거나 최소값을 제거하는 작업이 매우 빠르게 수행됩니다.
-
유연성: heapq는 리스트 기반의 힙을 제공하므로, 기본적인 리스트 연산과 유사하게 사용할 수 있습니다. 이는 Python의 다른 내장 자료 구조와 호환성을 제공하며, 다양한 문제 해결에 적용할 수 있습니다
