D+33 Lv2 더 맵게 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인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

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

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

풀이

(2) 클로드 풀이

function solution(scoville, K) {
   // 최소힙 구현
   class MinHeap {
       constructor() {
           this.heap = [];
       }
       
       push(value) {
           this.heap.push(value);
           let currentIndex = this.heap.length - 1;
           let parentIndex = Math.floor((currentIndex - 1) / 2);
           
           while (currentIndex > 0 && this.heap[parentIndex] > this.heap[currentIndex]) {
               [this.heap[currentIndex], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[currentIndex]];
               currentIndex = parentIndex;
               parentIndex = Math.floor((currentIndex - 1) / 2);
           }
       }
       
       pop() {
           if (this.heap.length === 0) return null;
           if (this.heap.length === 1) return this.heap.pop();
           
           const min = this.heap[0];
           this.heap[0] = this.heap.pop();
           let currentIndex = 0;
           
           while (true) {
               let minIndex = currentIndex;
               const leftIndex = currentIndex * 2 + 1;
               const rightIndex = currentIndex * 2 + 2;
               
               if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[minIndex]) {
                   minIndex = leftIndex;
               }
               if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[minIndex]) {
                   minIndex = rightIndex;
               }
               
               if (minIndex === currentIndex) break;
               
               [this.heap[currentIndex], this.heap[minIndex]] = [this.heap[minIndex], this.heap[currentIndex]];
               currentIndex = minIndex;
           }
           
           return min;
       }
   }
   
   const heap = new MinHeap();
   let count = 0;
   
   scoville.forEach(s => heap.push(s));
   
   while (heap.heap.length > 1 && heap.heap[0] < K) {
       const first = heap.pop();
       const second = heap.pop();
       heap.push(first + (second * 2));
       count++;
   }
   
   return heap.heap[0] >= K ? count : -1;
}

(1) 내 풀이 : Queue로 풀려고 함.

sort() 부분 때문에 시간 복잡도 O(N^2) 떠서 시간 초과됨
그리고 내 풀이에선 넣은 후에 sort를 넣었었는데, 테스트케이스에서도 틀렸다.
어떤 부분이 다른건지.. 확인을 천천히 해봐야할 것 같다.

어찌저찌 큐를 작성했는데, 이 시간초과 해결하기 위해선
최소힙을 구현해야 하는 것이었다.

우선순위 큐와 최소힙으로 풀 수 있다고 하는데 이 차이가 무엇인가 싶어서 검색해보았다.

class Queue {
    constructor(){
        this.tail =0;
        this.head =0;
        this.items=[]
    }
    dequeue(){
        if(this.tail === this.head){
            return undefined;
        }
        const item = this.items[this.head]
        delete this.items[this.head]
        this.head++
        return item
    }
    enqueue(element){
        this.items[this.tail]=element
        this.tail++
        this.sort()
    }
    length(){
        return this.tail-this.head
    }
    sort(){
        this.items.sort((a,b)=> a-b)
    }
}
function solution(scoville, K) {
    let answer = 0;
    let sum =0;
    let queue= new Queue();
    
    const scope =(first,second)=>{
        return first + 2*second
    }
    
    scoville.sort((a,b)=> a-b).forEach(item=> queue.enqueue(item))
    while(queue.length() > 1){
       sum=scope(queue.dequeue(),queue.dequeue())
       answer+=1
       if(sum >=K)return answer;
       queue.enqueue(sum)
    }
    return answer;
}