[ 𝗽𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗲𝗿𝘀 ] 더 맵게 -힙(Heap) | JavaScript

🎯 문제 설명

🧩 프로그래머스 Lv.2 - 더 맵게

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

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

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

🥅 제한 사항

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

🙆🏻‍♀️ 문제 풀이

1. 작은 스코빌 순으로 정렬해서 K보다 커진 순서를 빼내서 mix값을 구래서 다시 배열에 넣어서 정렬한다.
2. 모든 요소가 K보다 커질때까지 반복하면서 count를 센다.

Heap 정리했던 코드를 기반으로 MinHeap을 구현해서 코드를 짰음에도 테스트 케이스 중 통과하지 못하는 케이스들이 있었다.

예외처리 1

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 👉🏻 scoville = [0, 0, 0], K = 3, return 0

테스트 케이스를 추가하고 코드를 수정했다.

return minHeap.arr[0] >= K ? count : -1

모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우라면, mix 과정을 거쳐서 스코빌 지수가 1개만 남았을 때도 K보다 작은 경우를 말한다.
따라서, minHeap.arr[0]으로 mix 후 남은 지수마저 K보다 작은 경우 -1이 나오도록 조건문을 만들어 주었다.

예외처리 2

그럼에도 24번 케이스와, 효율성에서 실패를 해서 Heap 구현 부분을 샅샅히 뒤졌다....😢

    push(val) {
        this.arr.push(val);
        
        let idx = this.arr.length - 1;
        let parentIdx = Math.floor((idx - 1) / 2);
        while (idx > 0 && this.arr[parentIdx] > this.arr[idx]){
            [this.arr[idx], this.arr[parentIdx]] = [this.arr[parentIdx], this.arr[idx]];
            idx = parentIdx;
        }
    }

그 결과 push 메소드 안에 parentIdx가 갱신이 되지 않고 있다는 것을 발견했다...😂

👀 최종 코드

class MinHeap {
    constructor() {
        this.arr = [];
    }
    
    push(val) {
        this.arr.push(val);
        let idx = this.arr.length - 1;
        
        while (idx > 0){
            let parentIdx = Math.floor((idx - 1) / 2);
            if(this.arr[idx] >= this.arr[parentIdx]) break;
            [this.arr[idx], this.arr[parentIdx]] = [this.arr[parentIdx], this.arr[idx]];
            idx = parentIdx;
        }
    }
    
    pop() {
        if(this.arr.length === 1) return this.arr.pop();
        let min = this.arr[0];
        this.arr[0] = this.arr.pop();
        let cur = 0;
        
        while(cur * 2 + 1 < this.arr.length) {
            let minChild = cur * 2 + 2 < this.arr.length 
            && this.arr[cur * 2 + 2] < this.arr[cur * 2 + 1] ? 
            cur * 2 + 2 : cur * 2 + 1;
            
            if(this.arr[cur] < this.arr[minChild]) break;
        
            [this.arr[cur], this.arr[minChild]] = [this.arr[minChild], this.arr[cur]];
            cur = minChild;
        }
        return min;
    }
}

function solution(scoville, K) {
    const minHeap = new MinHeap();
    scoville.forEach(el => minHeap.push(el))
    
    let count = 0;
    while(minHeap.arr[0] < K && minHeap.arr.length > 1) {
        let fir = minHeap.pop();
        let sec = minHeap.pop();
        let mix = fir + (sec * 2);
        
        minHeap.push(mix);
        count++;
    }
    return minHeap.arr[0] >= K ? count : -1
}

• 기회가 되면 Heap 구조만 생각하면서 도움 없이 구현해봐야겠다.