1. Problem 📃
📚 출처 - 1927 - 최소 힙
문제 설명
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
입출력 예
| 예제 입력 | 예제 출력 |
|---|---|
| 9 0 12345678 1 2 0 0 0 0 32 | 0 1 2 12345678 0 |
2. Logic 👨🏫
이번 문제는 Heap을 이용해 해결하면 간단하지만, 처음에 python에서 Heap을 사용해 본 적이 없었기 때문에 조금 헤맸던 문제입니다.
단순히 Heap을 이용해 해결하면 매우 간단합니다. 코드를 먼저 보시죠~
3. Code 💻
1. 내가 푼 코드 😥 (시간 초과)
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
result = deque()
for i in range(N):
x = int(input())
if x == 0:
if len(result) == 0:
print(0)
else:
print(min(result))
result.popleft()
else:
if len(result) == 0:
result.append(x)
elif result[0] > x:
result.appendleft(x)
else:
result.append(x)2. 참고해서 푼 코드 😁
import heapq
import sys
input = sys.stdin.readline
N = int(input())
result = []
for i in range(N):
x = int(input())
if x == 0:
if len(result) == 0:
print(0)
else:
print(heapq.heappop(result))
else:
heapq.heappush(result, x)4. Feedback 📚
힙 자료구조
heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공합니다.
min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치합니다. 내부적으로 min heap 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제됩니다.
heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]예를 들어, 아래 그림은 위 공식을 만족시키는 간단한 min heap의 구조를 보여주고 있습니다.
1 ---> root
/ \
3 5
/ \ /
4 8 7모듈 임포트
import heapq최소 힙 생성
heapq 모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와줍니다.
그렇게 때문에, 그냥 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 합니다. 다시말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙입니다.
heap = []힙에 원소 추가
heapq 모듈의 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있습니다. 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넘깁니다.
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
>>> [1, 3, 7, 4]가장 작은 1이 인덱스 0에 위치하며, 인덱스 1(= k)에 위치한 3은 인덱스 3(= 2k + 1)에 위치한 4보다 크므로 힙의 공식을 만족합니다. 내부적으로 이진 트리에 원소를 추가하는 heappush() 함수는 O(logN)의 시간 복잡도를 가집니다.
힙에서 원소 삭제
heapq 모듈의 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있습니다. 원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴합니다.
print(heapq.heappop(heap))
print(heap)
1
[3, 4, 7]가장 작았던 1이 삭제되어 리턴되었고, 그 다음으로 작었던 3이 인덱스 0으로 올라왔습니다.
print(heapq.heappop(heap))
print(heap)
3
[4, 7]가장 작었던 3이 삭제되어 리턴되었고, 그 다음으로 작았던 4가 인덱스 0으로 올라왔습니다. 내부적으로 이진 트리로 부터 원소를 삭제하는 heappop() 함수도 역시 O(logN)의 시간 복잡도를 가집니다.
참고 자료 📩
Heap 사용법
