학습 목표: 상위 k개 유지와 우선순위 처리 문제에 힙을 적용합니다. 모든 예시는 주어진 매개변수를 처리해 정답을 반환하는 solution 함수로 완성합니다.
문제를 푸는 기준
전체 정렬이 아니라 최솟값이나 최댓값을 반복해 필요로 한다면 힙을 검토합니다. k번째 큰 값은 크기 k의 최소 힙으로 구합니다.
핵심 개념
| 개념 | 코딩테스트에서의 역할 |
|---|---|
| 최소 힙 | 루트가 전체 최솟값이 되도록 부모가 자식 이하를 유지합니다. |
| push | 마지막에 넣고 위로 올립니다. |
| pop | 루트를 꺼내고 마지막 값을 아래로 내립니다. |
대표 문제
k번째로 큰 값
정수 배열 numbers와 k가 주어집니다. 중복을 포함해 내림차순으로 정렬했을 때 k번째 값을 반환하세요.
함수 시그니처: solution(numbers, k)
제한사항
- numbers의 길이는 1 이상 200,000 이하입니다.
- k는 1 이상 numbers의 길이 이하입니다.
입출력 예
| 매개변수 | 반환값 |
|---|---|
[3,2,1,5,6,4], 2 | 5 |
[2,2,1], 2 | 2 |
풀이 설계
- 크기 k 이하의 최소 힙을 유지합니다.
- 새 값을 넣고 크기가 k보다 크면 최솟값을 제거합니다.
- 마지막 힙 루트를 반환합니다.
JavaScript 풀이
function solution(numbers, k) {
const heap = [];
const push = (value) => {
heap.push(value);
let i = heap.length - 1;
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const root = heap[0];
const last = heap.pop();
if (heap.length === 0) return root;
heap[0] = last;
let i = 0;
while (true) {
const left = i * 2 + 1;
const right = left + 1;
let next = i;
if (left < heap.length && heap[left] < heap[next]) next = left;
if (right < heap.length && heap[right] < heap[next]) next = right;
if (next === i) break;
[heap[i], heap[next]] = [heap[next], heap[i]];
i = next;
}
return root;
};
for (const number of numbers) {
push(number);
if (heap.length > k) pop();
}
return heap[0];
}복잡도
- 시간복잡도:
O(n log k) - 공간복잡도:
O(k) - 핵심 패턴: 크기 k의 최소 힙으로 가장 큰 k개 유지
- 경계 사례: 중복 값도 각각 한 순위로 계산
연습 문제
1. 작업 우선순위
우선순위가 높은 작업부터 처리 순서를 반환하세요.
힌트
비교 기준 힙
2. 두 묶음 합치기
가장 작은 두 묶음을 합치는 총비용을 구하세요.
힌트
최소 힙 두 번 pop
3. 상위 k 스트림
값마다 현재 상위 k개의 최솟값을 반환하세요.
힌트
크기 k 힙 유지
자주 하는 실수
- 부모 인덱스를 잘못 계산하는 실수
- pop에서 한쪽 자식만 비교하는 실수
- 최대 힙과 최소 힙을 반대로 고르는 실수
- 중복 값을 제거해 순위를 바꾸는 실수
핵심 정리
- 함수 시그니처와 반환 자료형을 먼저 확정합니다.
- 제한사항으로 가능한 시간복잡도를 판단합니다.
- 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
- 완성한
solution함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.
확인 문제
문제 14지선다
크기 k 최소 힙의 루트가 의미하는 값은?
문제 24지선다
대표 문제의 시간복잡도로 알맞은 것은?
문제 34지선다
k번째로 큰 값에서 사용한 핵심 패턴은?
문제 44지선다
대표 문제에서 반드시 확인할 경계 사례는?
문제 54지선다
이 과정의 정답 코드가 지켜야 할 계약은?
참고 자료
Last updated on