Programmers_42626 더 맵게

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(idx) {
        return Math.floor((idx - 1) / 2);
    }
    getLeftIdx(idx) {
        return idx * 2 + 1;
    }
    getRightIdx(idx) {
        return idx * 2 + 2;
    }

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

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        if (this.heap.length === 0) return null;

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();

        return min;
    }

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

        while (currIdx > 0 && this.heap[currIdx] < this.heap[parentIdx]) {
            this.swap(currIdx, parentIdx);
            currIdx = parentIdx;
            parentIdx = this.getParentIdx(currIdx);
        }
    }

    bubbleDown() {
        let currIdx = 0;
        let leftIdx = this.getLeftIdx(currIdx);
        let rightIdx = this.getRightIdx(currIdx);

        while (
            (leftIdx < this.size() &&
                this.heap[leftIdx] < this.heap[currIdx]) ||
            (rightIdx < this.size() && this.heap[rightIdx] < this.heap[currIdx])
        ) {
            const smallerIdx =
                this.heap[rightIdx] < this.heap[leftIdx] ? rightIdx : leftIdx;

            this.swap(currIdx, smallerIdx);
            currIdx = smallerIdx;
            leftIdx = this.getLeftIdx(currIdx);
            rightIdx = this.getRightIdx(currIdx);
        }
    }
}

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

    const scovilleHeap = new MinHeap();
    scoville.forEach((score) => {
        scovilleHeap.push(score);
    });

    while (scovilleHeap.size()) {
        const min = scovilleHeap.pop();
        if (min >= K) return count;

        const nextMin = scovilleHeap.pop();
        if (!nextMin) return -1;

        count++;
        scovilleHeap.push(min + nextMin * 2);
    }

    return -1;
}