📝 문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/42626
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
목표: 주어진 음식의 스코빌 지수가 K 이상이 되도록 섞어야하는 최소 횟수를 반환해야한다.
핵심 조건:
- 이 때 두 음식을 섞었을 때 스코빌 지수는 다음과 같다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
- 주어진 음식의 수는 2이상 1,000,000 이하이다.
- K는 0 이상 1,000,000,000 이하이다.
- 스코빌 지수는 0 이상 1,000,000 이하이다.
- 만약에 모든 스코빌 지수를 K 이상으로 만들 수 없다면 -1을 반환한다.
🔍 풀이 과정 (나만의 풀이 전략)
매번 가장 작은 값 2개를 꺼내서 연산하고 추가해줘야 하므로, 데이터가 추가/삭제될 때마다 자동으로 정렬 상태를 유지하는 자료구조인 최소 힙 자료구조를 활용한다.
스코빌 지수 배열의 요소들을 최소 힙에 순차적으로 삽입해보면 트리 구조 상에서 가장 작은 값인 1이 항상 루트 노드인 heap[0]에 위치하게 된다.
그렇다면 가장 스코빌 지수가 작은 두 음식을 힙에서 추출하고 섞어 힙에 삽입하는 과정은 다음과 같다.
- 힙의 루트 노드 (heap[0])가 K보다 작고, 힙에 남은 음식의 수가 2개 이상일 경우에 계속해서 음식을 섞는다.
- 가장 작은 값과 두 번째로 작은 값을 꺼내어 poll() 주어진 연산 공식에 따라 계산하여 새로운 스코빌 지수의 음식을 다시 힙에 넣는다. add() . 이 과정이 끝날 때 마다 answer 변수의 값을 1 증가 시킨다.
- 반복문이 끝나고 난 후에도 루트 노드의 값이 K보다 작다면 조건에 의해 -1을 반환한다.
scoville이 다음과 같이 주어졌을 때 [1, 2, 3, 9, 10, 12] 최소 힙의 변경 과정은 아래 그림과 같다.
1. 처음 힙의 초기 상태
2. 가장 맵지 않은 음식인 루트 노드를 poll() 및 bubbledown() 하는 과정
루트 노드인 1을 꺼내고 마지막 노드인 12를 루트 노드로 올린다.
루트로 올린 노드 12를 자식 노드인 2와 3과 비교하고 루트 노드보다 작고 이 중 2가 더 작으므로 2와 위치를 변경한다.
노드 12가 이동한 후에도 자식 노드들보다 더 큰 값이므로 자식 노드들 중 작은 값인 9와 위치를 변경한다. 이렇게 첫 번째 poll() 완료
3. 두 번째로 스코빌이 작은 값을 꺼내는 과정도 동일하게 진행한다.
추출한 가장 작은 스코빌 지수의 값은 순서대로 1, 2이다. 주어진 섞은 음식의 스코빌 지수 계산을 진행하면 1 + (2 * 2) = 5가 된다. 따라서 두 음식을 섞어 만든 새로운 음식 (스코빌 지수 5)를 힙에 삽입한다.
5를 힙의 마지막(heap[heap.size() - 1])에 삽입하고 bubbleup() 을 통해 위치를 정렬한다.
이렇게 첫 번째 루프가 종료되면서 answer 값을 1 증가시킨다. 여전이 K=7 보다 루트 노드의 값이 작기 때문에 동일한 방식으로 루프를 진행한다.
참고 자료: https://chamdom.blog/heap-using-js/
[자료구조] JavaScript로 힙(Heap) 구현하기
힙이란? 힙(heap) 은 완전 이진 트리의 일종 으로 특정한 규칙을 따라 부모 노드와 자식 노드 사이의 값이 정렬된다. 힙은 주로 우선순위 큐(Priority Queue) …
chamdom.blog
💻 코드 (Code)
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
getRoot() {
return this.heap[0];
}
swap(idx1, idx2) {
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
}
add(value) {
this.heap.push(value);
this.bubbleup();
}
bubbleup() {
let index = this.heap.length - 1;
let parentIndex = Math.floor((index - 1) / 2)
while (
parentIndex >= 0
&& this.heap[index] < this.heap[parentIndex]) {
this.swap(index, parentIndex);
index = parentIndex;
parentIndex = Math.floor((index - 1) / 2)
}
}
poll() {
if (this.heap.length === 1) {
return this.heap.pop();
}
const value = this.heap[0];
this.heap[0] = this.heap.pop(); // 마지막노드를 루트 노드로
this.bubbledown();
return value;
}
bubbledown() {
let index = 0;
let leftIndex = index * 2 + 1;
let rightIndex = index * 2 + 2;
while(
(leftIndex < this.heap.length
&& this.heap[leftIndex] < this.heap[index])
|| (rightIndex < this.heap.length
&& this.heap[rightIndex] < this.heap[index])) {
let smallIndex = leftIndex;
if (this.heap[rightIndex]
&& this.heap[smallIndex] > this.heap[rightIndex]) {
smallIndex = rightIndex;
}
this.swap(index, smallIndex);
index = smallIndex;
leftIndex = index * 2 + 1;
rightIndex = index * 2 + 2;
}
}
}
function solution(scoville, K) {
var answer = 0;
const heap = new MinHeap();
scoville.forEach((item) => {
heap.add(item);
})
let lowest = 0;
let secondLowest = 0;
while (heap.size() > 1 && heap.getRoot() < K) {
lowest = heap.poll();
secondLowest = heap.poll();
const mixScoville = lowest + (secondLowest * 2);
heap.add(mixScoville);
answer++;
}
if (heap.getRoot() < K) {
answer = -1;
}
return answer;
}
최적화된 코드
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
getRoot() {
return this.heap[0];
}
swap(idx1, idx2) {
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
}
add(value) {
this.heap.push(value);
this.bubbleup();
}
bubbleup() {
let index = this.heap.length - 1;
let parentIndex = Math.floor((index - 1) / 2)
while (
parentIndex >= 0
&& this.heap[index] < this.heap[parentIndex]) {
this.swap(index, parentIndex);
index = parentIndex;
parentIndex = Math.floor((index - 1) / 2)
}
}
poll() {
if (this.heap.length === 1) {
return this.heap.pop();
}
const value = this.heap[0];
this.heap[0] = this.heap.pop(); // 마지막노드를 루트 노드로
this.bubbledown();
return value;
}
bubbledown() {
let index = 0;
while(true) {
let leftIndex = index * 2 + 1;
let rightIndex = index * 2 + 2;
let smallIndex = index;
if (leftIndex < this.heap.length
&& this.heap[smallIndex] > this.heap[leftIndex])
{
smallIndex = leftIndex;
}
if (rightIndex < this.heap.length
&& this.heap[smallIndex] > this.heap[rightIndex])
{
smallIndex = rightIndex;
}
if (smallIndex === index) break;
this.swap(index, smallIndex);
index = smallIndex;
}
}
}
function solution(scoville, K) {
var answer = 0;
const heap = new MinHeap();
scoville.forEach((item) => {
heap.add(item);
})
let lowest = 0;
let secondLowest = 0;
while (heap.size() > 1 && heap.getRoot() < K) {
lowest = heap.poll();
secondLowest = heap.poll();
const mixScoville = lowest + (secondLowest * 2);
heap.add(mixScoville);
answer++;
}
if (heap.getRoot() < K) {
answer = -1;
}
return answer;
}
bubbledown() 메서드 코드를 조금 더 직관적이게 리팩토링하였고, 기존 조건문에서는 this.heap[rightIndex] 의 유무를 판단하였는데, 만약 오른쪽 자식 노드가 없다면 undefined가 된다. JS에서는 존재하지 않는 인덱스를 비교해도 런타임 에러가 아닌 false를 반환하기 때문에 왼쪽 자식만 있을 경우에 연산 로직이 꼬일 우려가 있어 rightIndex의 값이 현재 힙의 크기보다 작은지를 판단하도록 수정함.
❓ 꼬리 질문 및 복습 (Self-Q&A)
복습
최소 힙 개념 복습
최소 힙은 완전 이진 트리를 기반으로 하는 자료구조로, 최댓값이나 최솟값을 빠르게 찾아내기 위해 사용된다.
- 우선순위 조건: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같아야 한다 (A≤ B)
- 최소 힙의 루트 노드(heap[0])에는 트리 전체에서 가장 작은 값이 위치한다.
- 최소 힙은 오직 부모와 자식 간의 대소 관계만 보장할 뿐, 왼쪽 자식과 오른쪽 자식 간의 크기 순서는 정해져 있지 않다. (즉, 배열의 인덱스 순서대로 완벽히 정렬된 상태가 아니다.)
그렇다면 이진 탐색 트리와의 차이점은 무엇일까?
구분 최소 힙 (Min Heap) 이진 탐색 트리 (BST)
| 트리 형태 | 완전 이진 트리 (빈틈없이 채워짐) | 일반 이진 트리 (한쪽으로 치우칠 수 있음) |
| 정렬 방향 | 상하 관계 (부모 ≤ 자식) | 좌우 관계 (왼쪽자식 < 부모 < 오른쪽자식) |
| 목적 | 최솟값/최댓값을 O(1)만에 탐색 | 임의의 데이터를 O(log N)만에 탐색/정렬 |
마지막으로 배열을 이용해 완전 이진 트리를 표현할 수 있는 이유는 힙은 중간에 빈 노드가 존재하지 않는다. 따라서 연결 리스트가 아니라 일반 1차원 배열로 효율적으로 구현이 가능하다.
루트 노드의 인덱스를 0으로 시작할 때, 임의의 노드 인덱스가 i라면 다음 공식이 성립한다.
- 부모 노드의 인덱스: Math.floor((i - 1) / 2)
- 왼쪽 자식 노드의 인덱스: i * 2 + 1
- 오른쪽 자식 노드의 인덱스: i * 2 + 2
배열을 정렬 sort() 하여 가장 작은 값 두 개를 추출하고 추가하는 방식으로 구현 했을 때의 문제점
꼭 힙 자료구조를 택하지 않더라도 주어진 배열을 정렬하고 가장 작은 두 개의 값을 추출해서 섞고 새로운 값을 추가하는 방식을 반복한다면 문제 자체는 해결이 가능하다.
다만 효율성 테스트에서 문제가 생기는데 자바스크립트의 sort() 메서드는 Timsort 방식으로 O(N log N)의 시간 복잡도를 가진다. 최악의 경우 모든 음식을 다 섞어야 하므로 원소가 1개가 남을때 까지 N번 루프를 돌게 되므로 최종 시간 복잡도는 O(N^2 log N)이 된다.
해당 문제에서 N의 최대 값은 100만개이므로, 효율성 테스트에서 무조건 시간 초과가 발생하게 된다.
반면 최소 힙은 새 원소가 들어오거나 나갈 때 트리의 높이 만큼만 수직으로 이동하여 자리를 찾는다.
루프가 한 번 돌때
- 최소값 추출(poll()): 루트 노드를 빼고 맨 뒤 노드를 위로 올린 뒤 자식들과 비교해나간다. 이 때 높이만큼만 내려가므로 log N이 소요된다.
- 두 번째 최소값 추출 역시 마찬가지이다.
- 새 음식을 삽입하는 add() 역시 트리 높이만큼만 올라가므로 O(log N)의 시간 복잡도를 갖는다.
따라서 루프를 한 번 돌때 시간 복잡도가 O(log N)이고 이를 최대 N번 반복하면 O(N log N)의 시간 복잡도를 갖기 때문에 정렬하여 진행하는 것 보다 더 효율적이다.
💬 마무리하며
힙이라는 자료구조에 대해 과거에 배웠던 내용이었지만, 완전 까먹고 있어 자료구조에 대해 먼저 공부하고 문제를 풀이하게 되었습니다. 확실히 자료구조에 대한 이해가 기본기로 다져져 있어야 한다는 점을 깨닫게 된 문제였던 것 같습니다. 힙 자료 구조를 사용한다면 그리 어렵지 않게 해결할 수 있었던 문제였습니다.
앞으로도 파이팅입니다!
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 타겟 넘버 (Lv. 2 JavaScript) (0) | 2026.06.07 |
|---|---|
| [프로그래머스] 소수 찾기 (Lv. 2 JavaScript) (0) | 2026.06.06 |
| [프로그래머스] 가장 큰 수 (Lv. 2 JavaScript) (0) | 2026.06.01 |
| [프로그래머스] 올바른 괄호 (Lv. 2, JavaScript) (0) | 2026.05.29 |
| [프로그래머스] 기능개발 (Lv. 2, JavaScript) (1) | 2026.03.16 |