출처

https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이

주어진 자료에서 최소값을 구하고, 정렬하는 작업을 계속해서 수행해야 하기 때문에 힙 자료구조를 사용해야 한다.
js에는 내장된 라이브러리가 없기 때문에, class로 최소힙을 구현하는 연습도 하고 문제도 풀어보았다.

class MinHeap {
    constructor () {
        this.heap = []
    }
    
    size() {
        return this.heap.length;
    }
    
    swap(x, y) {
        [this.heap[x], this.heap[y]] = [this.heap[y], this.heap[x]]
    }
    
    push(v) {
        this.heap.push(v)
        
        let idx = this.size()-1
        // 부모 노드를 확인하면서, v가 더 작다면 위치를 서로 바꿔줌.
        while(idx > 0) {
            const parIdx = (idx-1)/2 >> 0
            if (this.heap[idx] >= this.heap[parIdx]) break
            
            this.swap(idx, parIdx)
            idx = parIdx
        }
        
        return this.heap     
    }
    
    pop() {
        if(this.size() === 0) return null
        
        // 1. 루트 노드와 맨 마지막 노드의 위치를 바꿈
        this.swap(0, this.size()-1)
        const minV = this.heap.pop()    // 1-1. 루트노드에 있던 최소값
        
        // 2. 루트 노드로 옮겨진 맨 마지막 노드를 다시 아래로 내려가면서 힙정렬.
        let idx = 0
        while(idx < this.size()) {
            const [ch1, ch2] = [idx*2+1, idx*2+2]
            
            // [주의]. 만약 swap해야 한다면, 두 자식 노드 중 더 작은 노드와 swap해야 힙의 조건을 유지할 수 있다.
            let smallest = idx
            
            // 2-1. 왼쪽 자식노드 검사. heap[idx]가 아니라, [smallest]로 비교해서 3개의 노드(부모, 왼자식, 오른자식 3개 중 최소값을 찾는다.)
            if (ch1 < this.size() && this.heap[smallest] > this.heap[ch1]) {
                smallest = ch1
            } 
            // 2-2. 오른쪽 자식 검사
            if (ch2 < this.size() && this.heap[smallest] > this.heap[ch2]) {
                smallest = ch2
            }
            
            // 2-3. 부모 노드가 두 자식노드보다 같거나 작다면 종료.
            if (smallest === idx) break;
            
            // 2-4. 아니라면, 두 자식노드 중 더 작은 노드와 스왑.
            this.swap(idx, smallest)
            idx = smallest
        }
        
        return minV
    }
}

function solution(scoville, K) {
    var answer = 0;
    
    const minHeap = new MinHeap()
    
    scoville.forEach(v=>{
        minHeap.push(v)
    })
    
    while (minHeap.size() > 1 && minHeap.heap[0] < K) {
        const [a, b] = [minHeap.pop(), minHeap.pop()]
        const mix = a + b*2
        minHeap.push(mix)
        answer ++
    }
    
    return minHeap.heap[0] >= K ? answer : -1;
}

배운점

• 힙도 간단하게 배열에 구현될 수 있지만, 배열의 인덱스의 의미가 부모와 자식의 관계라고 생각하는 것이 중요하다.