[프로그래머스] Lv.2 더 맵게 - JS

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

입출력 예 #1

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

실패

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

    let count = 0;
    while (scoville[scoville.length - 1] < K) {
        const first = scoville.pop();
        const second = scoville.pop();
        const newFood = first + second * 2;
        scoville.push(newFood);
        scoville.sort((a, b) => b - a);
        count++;
    }
    return scoville[0] >= K ? count : -1;
}

sort() 메소드로 인한 효율성 실패로 보임

결과

풀이

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]];
    }

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

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

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

    bubbleUp() {
        let childIdx = this.size() - 1;
        let parentIdx = this.getParentIdx(childIdx);

        while (this.heap[childIdx] < this.heap[parentIdx]) {
            this.swap(childIdx, parentIdx);
            childIdx = parentIdx;
            parentIdx = this.getParentIdx(parentIdx);
        }
    }

    bubbleDown() {
        let parentIdx = 0;
        let leftChildIdx = this.getLeftChildIdx(parentIdx);
        let rightChildIdx = this.getRightChildIdx(parentIdx);

        while (
            (leftChildIdx <= this.size() - 1 &&
                this.heap[leftChildIdx] < this.heap[parentIdx]) ||
            (rightChildIdx <= this.size() - 1 &&
                this.heap[rightChildIdx] < this.heap[parentIdx])
        ) {
            if (
                rightChildIdx <= this.size() - 1 &&
                this.heap[leftChildIdx] > this.heap[rightChildIdx]
            ) {
                this.swap(parentIdx, rightChildIdx);
                parentIdx = rightChildIdx;
            } else {
                this.swap(parentIdx, leftChildIdx);
                parentIdx = leftChildIdx;
            }
            leftChildIdx = this.getLeftChildIdx(parentIdx);
            rightChildIdx = this.getRightChildIdx(parentIdx);
        }
    }

    push(value) {
        this.heap.push(value);
        this.bubbleUp();
        return this.heap;
    }

    pop() {
        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;
    }
}

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

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

우선순위 큐를 위해 힙(완전 이진 트리) 구현

결과

문제 출처 - 알고리즘