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

모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞음

모두 섞었어도 K가 되지 못하면 -1, 아니라면 섞어야 하는 최소 횟수를 return

시간초과

function solution(scoville, K) {
    
    let cnt = 0;
    const arr = [];
    
    while(scoville.length > 1){
        scoville.sort((a,b)=> a-b)
        
        if(scoville[0] >= K){
            break
        }
        
        let firstVar = scoville.shift();
        let secondVar = scoville.shift();
        let newScoville = firstVar + secondVar*2;

        scoville.push(newScoville)
        cnt++
    }
    
    return scoville[0] < K ? -1 : cnt;
    
}

성능 문제:

• 매 반복마다 scoville.sort()로 전체를 정렬하면 입력이 큰 경우 시간초과
• 해결책은 매번 전체 정렬하지 않고 "최솟값 두 개를 빠르게 꺼낼 수 있는 자료구조(최소 힙/우선순위 큐)"를 사용해 복잡도를 크게 줄이는 것

MinHeap구현 후 적용 코드

class MinHeap {
  constructor() {
    this.heap = [];
  }

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

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

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (this.heap.length !== 0) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }
    return root;
  }

  /**
   *     0
   *   1    2
   *  3 4. 5 6
   */
  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      // 부모노드가 현재 탐색하는 노드보다 작거나 같다면 중단
      if (this.heap[parentIndex] <= this.heap[index]) {
        break;
      }
      // 부모노드가 현재 탐색하는 노드보다 크다면 위치 바꿔주기
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      
      // 왼쪽 자식과 오른쪽 자식이 제일 작은 인덱스의 값보다 작다면 자리 바꿔주기
      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex] < this.heap[smallest]
      ) {
        smallest = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex] < this.heap[smallest]
      ) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;
      
      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];

      index = smallest;
    }
  }
}

function solution(scoville, K) {
    const heap = new MinHeap();
    scoville.forEach(s => heap.push(s));
    
    let count = 0;
    while (heap.heap[0] < K) {
        if (heap.heap.length < 2) return -1; // 섞을 수 없는 경우

        const first = heap.pop();
        const second = heap.pop();
        const mixed = first + (second * 2);
        
        heap.push(mixed);
        count++;
    }
    
    return count;
}