[프로그래머스] JavaScript Lv2 - 더 맵게(42626)

개요

문제 이름: 더 맵게 (42626)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626
플랫폼: 프로그래머스
알고리즘 분류: 힙
소요 시간: 48시간(...)(2일 걸림)

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 우선순위 큐 또는 힙(Heap)을 사용하여 해결할 수 있는 알고리즘 문제입니다. 문제에서는 음식의 스코빌 지수를 모두 K 이상으로 만들기 위해 가장 맵지 않은 두 음식을 특별한 방법으로 섞어야 합니다. 이때 섞는 과정을 최소화하는 것이 목표입니다.

 

문제를 효과적으로 해결하기 위해서는 항상 스코빌 지수가 가장 낮은 두 음식을 선택해야 합니다. 이를 위해 우선순위 큐 또는 힙을 사용할 수 있습니다. 힙은 부모 노드의 값이 자식 노드의 값보다 항상 작은 최소 힙(Min Heap)을 사용하면 됩니다.

 

문제 해결 과정은 다음과 같습니다:

1. 주어진 음식의 스코빌 지수를 최소 힙에 삽입합니다.
2. 힙의 루트 노드(가장 맵지 않은 음식)의 스코빌 지수가 K 이상이 될 때까지 다음 과정을 반복합니다:
   1. 힙에서 가장 맵지 않은 음식(루트 노드)과 두 번째로 맵지 않은 음식(두 번째 노드)을 꺼냅니다.
   2. 두 음식을 섞어 새로운 음식을 만들고, 그 스코빌 지수를 계산합니다.
   3. 새로 만든 음식의 스코빌 지수를 힙에 삽입합니다.
   4. 섞은 횟수를 1 증가시킵니다.
3. 힙의 루트 노드의 스코빌 지수가 K 이상이 되면 섞은 횟수를 반환합니다.
4. 힙에 음식이 하나 남았는데도 스코빌 지수가 K 이상이 되지 않으면 -1을 반환합니다.

이 문제에서는 JavaScript의 내장 자료구조인 배열을 사용하여 최소 힙을 구현해야 합니다. 최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 이진 트리 구조입니다.

 

힙의 주요 연산은 다음과 같습니다:

• push: 새로운 요소를 힙에 삽입합니다. 삽입 후에는 힙의 속성을 유지하기 위해 위로 올라가며 부모 노드와 비교하고 필요한 경우 교환합니다.
• pop: 힙에서 가장 작은 요소(루트 노드)를 꺼내고 제거합니다. 제거 후에는 힙의 속성을 유지하기 위해 아래로 내려가며 자식 노드와 비교하고 필요한 경우 교환합니다.

 

힙

힙은 완전 이진 트리(Complete Binary Tree) 형태의 자료구조입니다.

 

힙에서는 각 노드의 값이 자식 노드들의 값보다 크거나 같은 최대 힙(Max Heap)과 각 노드의 값이 자식 노드들의 값보다 작거나 같은 최소 힙(Min Heap)이 있습니다.

 

힙은 배열을 사용하여 구현할 수 있습니다. 배열의 첫 번째 요소(인덱스 0)는 루트 노드이며, 각 노드의 왼쪽 자식은 '2 * i + 1', 오른쪽 자식은 '2 * i + 2'의 인덱스를 가집니다. 여기서 i는 부모 노드의 인덱스입니다.

 

힙은 삽입(insertion)과 삭제(deletion) 연산을 지원합니다. 삽입 연산은 새로운 요소를 힙의 마지막 위치에 추가한 후, 위로 올라가며 부모 노드와 비교하여 힙의 속성을 만족할 때까지 위치를 조정합니다. 삭제 연산은 루트 노드를 제거하고, 마지막 노드를 루트 노드로 이동시킨 후, 아래로 내려가며 자식 노드와 비교하여 힙의 속성을 만족할 때까지 위치를 조정합니다.

 

힙은 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용됩니다. 우선순위 큐는 우선순위가 가장 높은(또는 가장 낮은) 요소를 빠르게 찾아내고 제거할 수 있는 자료구조입니다.

 

최소 힙

최소 힙 - 출처: https://www.digitalocean.com/community/tutorials/min-heap-binary-tree

최소 힙은 힙의 한 종류로, 각 노드의 값(상위)이 자식 노드들의 값(하위)보다 작거나 같은 완전 이진 트리 형태의 자료구조입니다.

 

최소 힙에서는 루트 노드가 항상 최소값을 가집니다. 따라서 최소값을 빠르게 찾아내고 제거할 수 있습니다. 최소 힙의 삽입 연산은 새로운 요소를 힙의 마지막 위치에 추가한 후, 위로 올라가며 부모 노드와 비교하여 최소 힙의 속성을 만족할 때까지 위치를 조정합니다.

 

최소 힙의 삭제 연산은 루트 노드(최소값)를 제거하고, 마지막 노드를 루트 노드로 이동시킨 후, 아래로 내려가며 자식 노드와 비교하여 최소 힙의 속성을 만족할 때까지 위치를 조정합니다. 최소 힙은 우선순위 큐를 구현하는 데 사용되며, 최소값을 빠르게 찾아내고 제거해야 하는 문제에 적합합니다.

결론

힙과 최소 힙은 효율적인 자료구조로, 삽입과 삭제 연산의 시간 복잡도가 O(log n)입니다. 이는 힙의 높이가 log n이기 때문입니다. 따라서 힙을 사용하면 우선순위 큐와 같은 문제를 효율적으로 해결할 수 있습니다.

 

최소 힙은 최소값을 빠르게 찾아내야 하는 문제에 적합한 자료구조이며, 우선순위 큐, 다익스트라 알고리즘, 힙 정렬 등에 활용됩니다. 최소 힙을 구현할 때는 배열을 사용하여 완전 이진 트리 형태로 표현하고, 삽입과 삭제 연산 시 힙의 속성을 유지하도록 노드의 위치를 조정해야 합니다.

 

시도

1차 시도  (실패)

function solution(scoville, K) {
	let count = 0;

	while (scoville[0] < K) {
		if (scoville.length === 1) {
			return -1;
		}

		scoville.sort((a, b) => a - b);
		const first = scoville.shift();
		const second = scoville.shift();
		const mixed = first + second * 2;
		scoville.push(mixed);
		count++;
	}

	return count;
}

1차 시도에서는 배열을 사용하여 문제를 해결하려고 했습니다. 가장 맵지 않은 음식을 찾기 위해 배열을 오름차순으로 정렬하고, 첫 번째와 두 번째 음식을 꺼내 섞은 후 다시 배열에 추가하는 과정을 반복했습니다.

하지만 이 방법은 배열의 정렬에 O(n log n)의 시간 복잡도가 소요되기 때문에 효율적이지 않습니다. 따라서 효율성 테스트에서 시간 초과로 실패하게 됩니다. 공간 복잡도는 O(1)이지만, 시간 복잡도가 O(n^2 log n)으로 매우 비효율적입니다.

 

2차 시도  (실패)

function solution(scoville, K) {
	let count = 0;
	scoville.sort((a, b) => a - b);

	while (scoville[0] < K) {
		if (scoville.length === 1) return -1;

		const first = scoville.shift();
		const second = scoville.shift();
		const mixed = first + second * 2;

		scoville.push(mixed);
		scoville.sort((a, b) => a - b);
		count++;
	}

	return count;
}

2차 시도에서는 배열을 오름차순으로 한 번만 정렬한 후, 가장 맵지 않은 두 음식을 꺼내 섞고 다시 배열에 추가하는 과정을 반복했습니다. 섞은 후에는 배열을 다시 정렬해야 합니다.

하지만 이 방법도 여전히 배열의 정렬에 O(n log n)의 시간 복잡도가 소요되므로 효율성 테스트에서 시간 초과로 실패합니다. 공간 복잡도는 O(1)이지만, 시간 복잡도가 O(n^2 log n)으로 여전히 비효율적입니다.

 

3차 시도 (성공)

// MinHeap 클래스를 정의하는 코드입니다. 이 클래스는 최소 힙을 구현합니다.
class MinHeap {
    // constructor는 클래스의 생성자 메서드로, 힙을 저장할 빈 배열 heap을 초기화합니다.
	constructor() {
		this.heap = [];
	}
    
	// getParentIndex 메서드는 주어진 인덱스의 부모 노드 인덱스를 계산하여 반환합니다.
	getParentIndex(index) {
		return Math.floor((index - 1) / 2);
        // 부모 노드의 인덱스는 (index - 1) / 2의 내림 값입니다.
	}

	// getLeftChildIndex 메서드는 주어진 인덱스의 왼쪽 자식 노드 인덱스를 계산하여 반환합니다.
	getLeftChildIndex(index) {
		return 2 * index + 1;
        // 왼쪽 자식 노드의 인덱스는 2 * index + 1입니다.
	}

	// getRightChildIndex 메서드는 주어진 인덱스의 오른쪽 자식 노드 인덱스를 계산하여 반환합니다.
	getRightChildIndex(index) {
		return 2 * index + 2;
        // 오른쪽 자식 노드의 인덱스는 2 * index + 2입니다.
	}

	// swap 메서드는 힙의 두 노드의 값을 교환합니다.
	swap(index1, index2) {
		const temp = this.heap[index1];
		this.heap[index1] = this.heap[index2];
		this.heap[index2] = temp;
        // 임시 변수 temp를 사용하여 index1의 값을 저장합니다.
        // 그리고 index1에 index2의 값을 할당한 후 index2에 temp의 값을 할당합니다.
	}

	// push 메서드는 새로운 요소를 힙에 삽입합니다.
	push(value) {
		this.heap.push(value);
        
		// currentIndex는 삽입된 요소의 인덱스이고, parentIndex는 부모 노드의 인덱스입니다.
		let currentIndex = this.heap.length - 1;
		let parentIndex = this.getParentIndex(currentIndex);

		// 삽입된 요소가 루트 노드가 아니고, 부모 노드의 값이 삽입된 요소의 값보다 크다면 교환합니다.
		// 교환 후에는 currentIndex를 parentIndex로 업데이트하고, 다시 parentIndex를 구합니다.
		while (currentIndex > 0 && this.heap[parentIndex] > this.heap[currentIndex]) {
			this.swap(currentIndex, parentIndex);
			currentIndex = parentIndex;
			parentIndex = this.getParentIndex(currentIndex);
		}
		// 이 과정을 반복하여 힙의 속성을 유지합니다.
	}

	// pop 메서드는 힙에서 가장 작은 요소(루트 노드)를 꺼내고 제거합니다.
	pop() {
		// 힙이 비어있다면 null을 반환합니다.
		if (this.isEmpty()) return null;
        
        // 힙에 요소가 하나밖에 없다면 해당 요소를 제거하고 반환합니다.
		if (this.heap.length === 1) return this.heap.pop();

		// 루트 노드의 값을 root 변수에 저장하고, 힙의 마지막 요소를 루트 노드로 이동시킵니다.
		const root = this.heap[0];
		this.heap[0] = this.heap.pop();

		// currentIndex는 현재 노드의 인덱스이고, leftChildIndex와 rightChildIndex는 각각 왼쪽과 오른쪽 자식 노드의 인덱스입니다.
		let currentIndex = 0;
		let leftChildIndex = this.getLeftChildIndex(currentIndex);
		let rightChildIndex = this.getRightChildIndex(currentIndex);

		// 현재 노드의 값이 왼쪽 자식이나 오른쪽 자식보다 크다면 교환이 필요합니다.
		while (
			(leftChildIndex < this.heap.length && this.heap[currentIndex] > this.heap[leftChildIndex]) ||
			(rightChildIndex < this.heap.length && this.heap[currentIndex] > this.heap[rightChildIndex])
		) {
			// 왼쪽 자식과 오른쪽 자식 중 더 작은 값을 가진 노드와 교환합니다.
			const smallerChildIndex =
				rightChildIndex >= this.heap.length || this.heap[leftChildIndex] < this.heap[rightChildIndex]
					? leftChildIndex
					: rightChildIndex;
			this.swap(currentIndex, smallerChildIndex);
            
            // 교환 후에는 currentIndex를 교환한 자식 노드의 인덱스로 업데이트하고, 다시 leftChildIndex와 rightChildIndex를 구합니다.
			currentIndex = smallerChildIndex;
			leftChildIndex = this.getLeftChildIndex(currentIndex);
			rightChildIndex = this.getRightChildIndex(currentIndex);
            
            // 이 과정을 반복하여 힙의 속성을 유지합니다.
		}

		// 마지막으로 제거된 루트 노드의 값 root를 반환합니다.
		return root;
	}

	// isEmpty 메서드는 힙이 비어있는지 확인합니다.
	isEmpty() {
    	// 힙의 길이가 0이면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
		return this.heap.length === 0;
	}
}


// solution 함수는 주어진 스코빌 지수 배열 scoville과 목표 스코빌 지수 K를 받습니다.
// 그리고 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환합니다.
function solution(scoville, K) {
	// 먼저 MinHeap 클래스의 인스턴스 minHeap을 생성합니다.
	const minHeap = new MinHeap();
	
    // for 반복문을 사용하여 scoville 배열의 모든 요소를 minHeap에 삽입합니다.
	for (let i = 0; i < scoville.length; i++) {
		minHeap.push(scoville[i]);
	}

	// count 변수를 초기화하여 섞은 횟수를 저장합니다.
	let count = 0;

	// while 반복문을 사용하여 minHeap의 루트 노드(가장 작은 스코빌 지수)가 K 미만인 동안 반복합니다.
	while (minHeap.heap[0] < K) {
    
    	// 만약 minHeap에 요소가 1개밖에 없다?
        // 그러면 합할 개수 부족으로 모든 음식을 K 이상으로 만들 수 없으므로 -1을 반환합니다.
		if (minHeap.heap.length === 1) return -1;

		// minHeap에서 가장 작은 스코빌 지수 first와 두 번째로 작은 스코빌 지수 second를 꺼냅니다.
		const first = minHeap.pop();
		const second = minHeap.pop();
        
        // 섞은 음식의 스코빌 지수 mixed를 계산합니다.
		const mixed = first + second * 2;

		// mixed를 다시 minHeap에 삽입합니다.
		minHeap.push(mixed);
        
        // 섞은 횟수 count를 1 증가시킵니다.
		count++;
	}
    
	// while 반복문이 종료되면 모든 음식의 스코빌 지수가 K 이상이 된 것입니다.
    // 그러므로 섞은 횟수 count를 반환합니다.
	return count;
}

3차 시도에서는 직접 최소 힙을 구현하여 문제를 해결했습니다. 최소 힙을 사용하면 가장 맵지 않은 음식을 빠르게 찾을 수 있기 때문에 효율적으로 문제를 해결할 수 있습니다.

 

최소 힙은 다음과 같은 메서드를 가지고 있습니다

• getParentIndex: 부모 노드의 인덱스를 반환합니다.
• getLeftChildIndex: 왼쪽 자식 노드의 인덱스를 반환합니다.
• getRightChildIndex: 오른쪽 자식 노드의 인덱스를 반환합니다.
• swap: 두 노드의 값을 교환합니다.
• push: 새로운 요소를 힙에 삽입합니다.
• pop: 힙에서 가장 작은 요소(루트 노드)를 꺼내고 제거합니다.
• isEmpty: 힙이 비어있는지 확인합니다.

solution 함수에서는 먼저 주어진 스코빌 지수를 최소 힙에 삽입합니다. 그리고 힙의 루트 노드(가장 맵지 않은 음식)의 스코빌 지수가 K 이상이 될 때까지 반복합니다. 반복 과정에서는 힙에서 가장 맵지 않은 두 음식을 꺼내 섞고, 섞은 음식을 다시 힙에 삽입합니다. 이때 섞은 횟수를 카운트합니다.

 

최소 힙을 사용하면 가장 맵지 않은 음식을 찾는 데 O(1)의 시간 복잡도가 소요되고, 힙에 삽입과 삭제는 O(log n)의 시간 복잡도가 소요됩니다. 따라서 전체 시간 복잡도는 O(n log n)이 됩니다. 공간 복잡도는 최소 힙을 저장하기 위해 O(n)이 됩니다.

 

사족

이런 게 2단계에서 나올 줄은 상상도 못했습니다. 덕분에 2일이라는 시간을 소모했네요. ㅠㅠ