Note
힙(Heap) 자료구조를 활용하여 최소 힙을 구현하는 문제입니다.
문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
문제 링크: https://www.acmicpc.net/problem/1927
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 2³¹보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제
예제 입력 1:
9
0
12345678
1
2
0
0
0
0
32
예제 출력 1:
0
1
2
12345678
0
문제 분석
이 문제는 최소 힙을 구현하는 기본 문제입니다.
핵심 포인트
- 최소 힙 사용: Python의
heapq모듈을 사용하여 최소 힙 구현 - 삽입 연산: 자연수 x가 주어지면 힙에 추가
- 삭제 연산: 0이 주어지면 최소값을 제거하고 출력
- 빈 힙 처리: 힙이 비어있을 때 0을 출력
해결 방법
Python의 heapq 모듈을 사용하여 최소 힙을 구현합니다:
heapq.heappush(): 원소 추가heapq.heappop(): 최소값 제거 및 반환- 빈 힙 체크:
len(heap) == 0또는not heap
코드 구현
제공된 코드
import heapq
import sys
readline = sys.stdin.readline
queue = []
n = int(readline())
for _ in range(n):
v = int(readline())
if v == 0:
if len(queue) == 0:
print(0)
else:
min = heapq.heappop(queue)
print(min)
else:
heapq.heappush(queue, v)코드 분석
1. 입력 처리
import heapq
import sys
readline = sys.stdin.readline
queue = []
n = int(readline())- 입력 최적화를 위해
sys.stdin.readline()사용 heapq모듈 import- 빈 리스트를 힙으로 사용
2. 연산 처리
for _ in range(n):
v = int(readline())
if v == 0:
if len(queue) == 0:
print(0)
else:
min = heapq.heappop(queue)
print(min)
else:
heapq.heappush(queue, v)동작 과정:
v == 0: 최소값 제거 및 출력- 힙이 비어있으면 0 출력
- 비어있지 않으면
heappop()으로 최소값 제거 및 출력
v != 0: 힙에 원소 추가heappush()로 원소 추가
개선된 코드
더 Pythonic하게 작성한다면:
import heapq
import sys
readline = sys.stdin.readline
n = int(readline())
heap = []
for _ in range(n):
x = int(readline())
if x == 0:
if heap:
print(heapq.heappop(heap))
else:
print(0)
else:
heapq.heappush(heap, x)개선 사항:
- 변수명을 더 명확하게 (
queue→heap,v→x) len(queue) == 0→not heap(더 Pythonic)min은 내장 함수명이므로 변수명으로 사용하지 않음
시간 및 공간 복잡도
시간 복잡도
- 삽입 연산: O(log n) -
heappush()는 O(log n) - 삭제 연산: O(log n) -
heappop()은 O(log n) - 전체: O(n log n) - n개의 연산
공간 복잡도
- 힙 저장: O(n) - 최대 n개의 원소 저장
- 전체: O(n)
예제 동작 과정
예제 입력 1: n=9
연산 순서:
0→ 힙이 비어있음 → 출력:012345678→ 힙에 추가 → 힙:[12345678]1→ 힙에 추가 → 힙:[1, 12345678]2→ 힙에 추가 → 힙:[1, 2, 12345678]0→ 최소값 제거 → 출력:1, 힙:[2, 12345678]0→ 최소값 제거 → 출력:2, 힙:[12345678]0→ 최소값 제거 → 출력:12345678, 힙:[]0→ 힙이 비어있음 → 출력:032→ 힙에 추가 → 힙:[32]
최종 출력:
0
1
2
12345678
0
힙의 동작 원리
힙 구조
힙은 완전 이진 트리로, 배열로 표현됩니다:
1
/ \
2 12345678
배열: [1, 2, 12345678]
삽입 과정
2를 추가할 때:
- 마지막 위치에 추가:
[1, 12345678, 2] - 부모와 비교하여 힙 속성 유지:
[1, 2, 12345678]
삭제 과정
최소값 1을 제거할 때:
- 루트(1)를 마지막 노드(2)로 교체:
[2, 12345678] - 힙 속성을 유지하기 위해 아래로 내림: 이미 힙 속성 만족
자세한 설명은 힙 자료구조 포스트를 참고하세요.
주의사항
1. 빈 힙 처리
힙이 비어있을 때 heappop()을 호출하면 IndexError가 발생합니다:
# 올바른 방법
if heap:
print(heapq.heappop(heap))
else:
print(0)2. 변수명 주의
min은 Python의 내장 함수이므로 변수명으로 사용하지 않는 것이 좋습니다:
# 피해야 할 방법
min = heapq.heappop(queue)
# 권장 방법
min_value = heapq.heappop(heap)
# 또는
value = heapq.heappop(heap)3. 입력 최적화
N이 최대 100,000이므로 input() 대신 sys.stdin.readline()을 사용해야 합니다.
관련 알고리즘
- 힙 (Heap) 자료구조
- Python 입력 최적화
- 우선순위 큐 (Priority Queue)