난이도 : 실버 2
유형 : 우선순위 큐
https://www.acmicpc.net/problem/11279
단계별로 풀어보기 - 우선순위 큐 유형에 첫번째 문제이다.
우선순위 큐, heap에 대한 개념이 필요해 정리 후 풀겠다.
우선순위 큐 & Heap 정리
1. 우선순위 큐(Priority Queue)란?
- 일반적인 큐(Queue)는 "먼저 들어온 데이터 먼저 나감" → FIFO (First In First Out)
- 우선순위 큐는 먼저 들어온 순서보다 "우선순위가 높은 데이터"를 먼저 꺼낸다.
예시
( 우선순위, 데이터 )
| 입력 순서 | 우선순위 큐 출력 순서 |
|---|---|
| (3, "C") | (1, "A") |
| (1, "A") | (2, "B") |
| (2, "B") | (3, "C") |
2. 우선순위 큐 구현 방법
- 정렬된 리스트로 구현하면 → 비효율적이다. (매번 정렬 필요)
- Heap 자료구조로 구현 →
O(log N)속도로 삽입 & 삭제 가능
3. Heap이란?
- 완전 이진 트리의 일종
- 항상 최댓값 또는 최솟값을 빠르게 꺼낼 수 있도록 정렬된 트리
✔️ 종류
| 종류 | 설명 |
|---|---|
| 최소 힙 (Min Heap) | 부모 노드 ≤ 자식 노드 (가장 작은 값이 루트) |
| 최대 힙 (Max Heap) | 부모 노드 ≥ 자식 노드 (가장 큰 값이 루트) |
최소, 최대라는 말이 루트 노드를 기준으로 붙는다고 기억하면 편할 것 같다.
4. Python에서 Heap 쓰기 (heapq)
- Python의
heapq모듈은 최소 힙(Min Heap)만 지원한다. - 리스트를 힙처럼 사용 가능
heapq 메소드
- heapq.heappush(heap, item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
- heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
Min Heap 기본 예시
import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
print(heapq.heappop(heap)) # 1 (가장 작은 값부터 꺼냄)Max Heap 구현하려면 (음수로 대응)
import heapq
heap = []
heapq.heappush(heap, -4)
heapq.heappush(heap, -1)
heapq.heappush(heap, -7)
print(-heapq.heappop(heap)) # 7 (가장 큰 값 꺼냄)튜플로 우선순위 지정
import heapq
heap = []
heapq.heappush(heap, (2, 'C'))
heapq.heappush(heap, (1, 'A'))
heapq.heappush(heap, (3, 'B'))
print(heapq.heappop(heap)) # (1, 'A') → 가장 우선순위 낮은 숫자5. 시간 복잡도 비교
| 연산 | 일반 리스트 | Heap (heapq) |
|---|---|---|
| 삽입 (push) | O(1) | O(log N) |
| 삭제 (pop) | O(N) | O(log N) |
| 우선순위 조회 | O(N) | O(1) |
→ heapq는 효율적인 우선순위 큐 구현을 가능하게 한다!
우선 이정도 익히고 문제를 풀어보겠다.
문제 접근
연산의 개수 N을 입력받고 자연수 or 0을 입력 받는다.
자연수를 입력 받았다면 배열에 x라는 값을 넣는(추가하는) 연산이고
0을 입력받았다면, 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하라는 프로그램을 만들자.
핵심 아이디어
최대 힙이 필요하지만, Python의 heapq는 최소 힙만 제공한다.
따라서 x를 넣을 때 -x로 바꿔서 넣고, 꺼낼 때 다시 -를 붙이면 최대 힙처럼 동작한다.
해답 및 풀이
import heapq
import sys
input = sys.stdin.readline
N = int(input())
heap = []
for _ in range(N):
x = int(input())
# 만약 x가 자연수라면 배열에 x를 추가
if x == x > 0:
heapq.heappush(heap, -x)
# 만약 x가 0 이라면 배열에서 가장 큰 값 출력 및 그 값을 배열에서 제거.
elif x == 0:
if heap:
print(-heapq.heappop(heap))
else:
print(0)
maxheap을 구현할때
push할때 x 앞에 마이너스를 붙여주고,
heappush(heap, -x)
pop할때 heapq.heappop 함수 앞에 마이너스를 붙여주는 것을 기억하자
-heapq.heappop(힙 배열))
Frontend Engineers