[프로그래머스/더 맵게] - JS로 힙 직접 구현해보기

문제 설명

---

프로그래머스

 

시간 복잡도

---

힙을 사용하지 않고, 코드를 구현했었는데, 효율성까지 통과해야하는 문제였기 때문에 힙을 사용해서 구현을 해야만 효율성을 모두 통과할 수 있었다. 

 

처음에는 힙을 사용하지 않고 배열을 매번 정렬했었기에 nlogn의 시간복잡도가 걸렸지만, 힙을 사용함으로써 logn으로 시간복잡도를 줄일 수 있었다. 

 

 

알고리즘 설계

---

처음 작성한 코드는 아래와 같다. 

function solution(scoville, K) {
​​​​let answer = 0; // 섞어야 하는 최소 횟수
​​​​
​​​​// 모든 값이 K 이상인지 확인하기
​​​​while(true) {
​​​​​​​​// 순차정렬
​​​​​​​​scoville = scoville.sort((a, b) => a - b);
​​​​​​​​// 섞은 음식의 스코빌 지수
​​​​​​​​let newScoville = scoville[0] + (scoville[1] * 2);
​​​​​​​​// 첫 번째 값과 두 번째 값 제거
​​​​​​​​scoville.splice(0, 2);
​​​​​​​​// 계산한 값 맨 앞에 추가
​​​​​​​​scoville.unshift(newScoville);
​​​​​​​​answer++;
​​​​​​​​
​​​​​​​​// 모든 값이 K 이상인 경우
​​​​​​​​if(scoville.filter((el) => el >= K).length === scoville.length) break;
​​​​​​​​// 배열의 길이가 1 이하인 경우 종료
​​​​​​​​if(scoville.length <= 1) break;
​​​​}
​​​​
​​​​// 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우: -1
​​​​for (let el of scoville) {
​​​​​​​​if (el < K) {
​​​​​​​​​​​​answer = -1;
​​​​​​​​​​​​break;
​​​​​​​​}
​​​​}   
​​​​
​​​​return answer;
}

 

틀린 부분

---

1. 순차정렬이 아닌 우선순위 큐 사용하기

배열을 매번 정렬하는 대신 힙을 사용하면 nlogn의 시간복잡도를 logn으로 줄일 수 있다.

 

2. 조건 확인 최적화하기

배열 전체를 순회하지 않고, 섞은 결과로 생긴 새로운 음식의 스코빌 지수가 K이상인 경우 나머지도 K이상임이 보장된다. 

 

다른 풀이

---

class MinHeap {
​​constructor() {
​​​​this.heap = [];
​​}

​​size() {
​​​​return this.heap.length;
​​}

​​swap(idx1, idx2) {
​​​​[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
​​​​return this.heap;
​​}

​​getParentIdx(childIdx) {
​​​​return Math.floor((childIdx - 1) / 2);
​​}

​​getLeftChildIdx(parentIdx) {
​​​​return parentIdx * 2 + 1;
​​}

​​getRightChildIdx(parentIdx) {
​​​​return parentIdx * 2 + 2;
​​}

​​heapPop() {
​​​​const heapSize = this.size();
​​​​if (!heapSize) return null;
​​​​if (heapSize === 1) return this.heap.pop();

​​​​const value = this.heap[0];
​​​​this.heap[0] = this.heap.pop();
​​​​this.bubbleDown();
​​​​return value;
​​}

​​heapPush(value) {
​​​​this.heap.push(value);
​​​​this.bubbleUp();

​​​​return this.heap;
​​}

​​bubbleUp() {
​​​​let child = this.size() - 1;
​​​​let parent = this.getParentIdx(child);

​​​​while (this.heap[child] < this.heap[parent]) {
​​​​​​this.swap(child, parent);
​​​​​​child = parent;
​​​​​​parent = this.getParentIdx(parent);
​​​​}
​​}

​​bubbleDown() {
​​​​let parent = 0;
​​​​let leftChild = this.getLeftChildIdx(parent);
​​​​let rightChild = this.getRightChildIdx(parent);

​​​​while (
​​​​​​(leftChild <= this.size() - 1 && this.heap[leftChild] < this.heap[parent]) ||
​​​​​​(rightChild <= this.size() - 1 && this.heap[rightChild] < this.heap[parent])
​​​​) {
​​​​​​if (rightChild <= this.size() - 1 && this.heap[leftChild] > this.heap[rightChild]) {
​​​​​​​​this.swap(parent, rightChild);
​​​​​​​​parent = rightChild;
​​​​​​} else {
​​​​​​​​this.swap(parent, leftChild);
​​​​​​​​parent = leftChild;
​​​​​​}
​​​​​​leftChild = this.getLeftChildIdx(parent);
​​​​​​rightChild = this.getRightChildIdx(parent);
​​​​}
​​}
}

function solution(scoville, K) {
​​let count = 0;
​​const heap = new MinHeap();
​​scoville.forEach((el) => heap.heapPush(el));

​​while (heap.heap[0] < K && heap.size() > 1) {
​​​​count++;
​​​​heap.heapPush(heap.heapPop() + heap.heapPop() * 2);
​​}
​​return heap.heap[0] >= K ? count : -1;
}

 

 

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖