문제

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

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

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

입력

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

출력

2

제한 사항

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

내가 했던 풀이 방법

1. MinHeap 클래스를 구현해준다. MinHeap에는 add, remove, mix가 있다. add와 remove는 일반적인 최소 힙의 요소를 추가하거나 제거해주는 방법을 사용하였다. mix는 음식을 섞어주는 함수로, heap의 길이가 2보다 작을 경우 -1을 반환해주고, 가장 최솟값(0번째 index)이 K보다 클 경우에는 0을 반환한다. 그 외로는 최솟값 2개를 삭제하고, 두 값을 스코빌 지수를 구하는 공식에 맞춰 계산하여 다시 heap에 추가해준다. 그 다음 1을 반환해준다.
2. scoville 배열에 모든 요소를 heap에 추가해준다.
3. mix를 한 값이 -1 또는 0일 때까지 반복한다. 반복할 때마다 answer를 1씩 증가시켜준다. return 결과가 0일 경우는 해당 요소가 전부 K 이상임을 나타내는 것이므로, 연산이 끝났음을 의미한다. 추가 연산 없이 반복문을 탈출한다. result가 -1일 때는 두 가지 상황이 될 수 있다. 첫 번째는 섞을 음식이 충분하지 않아서 K를 만들지 못할 때, 섞을 음식이 없지만 K를 넘었을 때이다. 그러므로, -1인 경우 최솟값이 K 이상인 경우는 반복문을 탈출하고, K보다 작은 경우 answer를 -1로 바꿔준 뒤 반복문을 탈출한다.
4. answer를 반환한다.

코드

function solution(scoville, K) {
    var answer = 0;
    let heap = new MinHeap();
    for(let i=0; i<scoville.length; i++) {
        heap.add(scoville[i]);
    }

    while(true) {
        let result = heap.mix(K);
        if(result===-1) {
            if(heap.get()[0]>=K) break;
            else {
                answer = -1;
                break;
            }
        } else if(result===0) {
            break;
        }
        answer++;
    }
    return answer;
}

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    add(value) {
        this.heap.push(value);
        let current = this.heap.length-1;
        let parent = Math.floor((current-1)/2);
        while(current>0 && this.heap[parent]>this.heap[current]) {
            [this.heap[parent], this.heap[current]] = [this.heap[current], this.heap[parent]];
            current = parent;
            parent = Math.floor((current-1)/2);
        }
    }
    
    remove() {
        if(this.heap.length===1) return this.heap.pop();
        let value = this.heap[0];
        this.heap[0] = this.heap.pop();
        let current = 0;
        let left = current*2+1;
        let right = current*2+2;
        while((this.heap[left] && this.heap[left]<this.heap[current]) || (this.heap[right] && this.heap[right]<this.heap[current])) {
            if (right >= this.heap.length || this.heap[left] < this.heap[right]) {
                [this.heap[left], this.heap[current]] = [this.heap[current], this.heap[left]];
                current = left;
            } else {
                [this.heap[right], this.heap[current]] = [this.heap[current], this.heap[right]];
                current = right;
            }
            left = current*2+1;
            right = current*2+2;
        }
        return value;
    }
    
    mix(value) {
        if(this.heap.length<2) return -1;
        else if(this.heap[0]>=value) return 0;
        else {
            let min1 = this.remove();
            let min2 = this.remove();
            this.add(min1+(min2*2));
        }
        return 1;
    }
    
    get() {
        return this.heap;
    }
}

회고

오랜만에 힙 구현하려다가 제거하는 코드가 떠오르지 않아서 다른 코드들을 참고해보려고 했는데 제대로 이해되지 않아서 미뤄뒀던 문제. 힙이 어렵다기 보다는 그때 환경이 풀기 좋은 환경이 아니였다. PC도 아니었고... 집에서 푼 것도 아니라... 집와서 푸니까 쉽게 풀었던 것 같다. 확실히 문제 풀이에 환경이 크게 좌지우지하는 것 같다.