✅ 코드

• 실패 코드 (테스트 케이스는 통과하지만, 시간초과 이슈)

  function solution(scoville, K) {
      let count = 0
      
      scoville.sort((a, b) => a - b); 
      
      while(scoville[0] < K){
          if(scoville.length < 2) return -1
          count++
          
          let temp =  scoville.shift() + scoville.shift() * 2;
          
          let index = scoville.findIndex((item) => item >= temp)
          
          if(index === -1) scoville.push(temp)
          else scoville.splice(index, 0, temp)
      }
  
      return count;
  }

• 성공 코드 (시간초과 해결을 위해 heap 이용)

  class Heap {
      constructor(){
          this.heap = [] // 선언 및 초기화
      }
      
      swap(i,j){
          [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]] // 구조분해할당
      }
      
      getParentIndex(i){
          return Math.floor((i-1)/2) // 루트의 부모는 존재하지 않으므로 음수 return
      }
      getLeftChildIndex(i){
          return 2*i + 1
      }
      getRightChildIndex(i){
          return 2*i + 2
      }
      
      heappush(v){
          this.heap.push(v) // python의 heapq.heappush와 유사하게
          this.bubbleUp()
      }
      
      bubbleUp(){ // 부모와 비교하며 위치를 상향 조정하는 함수
          let index = this.heap.length-1
          let parent_index = this.getParentIndex(index)
          
          while(index > 0 && this.heap[index] < this.heap[parent_index]){ // 부모가 더 크다면 교환
              this.swap(index, parent_index)
              index = parent_index
              parent_index = this.getParentIndex(index)
          }
      }
      
      heappop(){
        if(this.heap.length === 0) return null
        if(this.heap.length === 1) return this.heap.pop()
          
        let min = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.bubbleDown(0)
  
        return min
        
      }
      
      bubbleDown(index){ // 자식과 비교하며 위치를 하향 조정하는 함수
          let left = this.getLeftChildIndex(index)
          let right = this.getRightChildIndex(index)
          
          let min_index = index // 현재 인덱스를 가장 작은 인덱스 값으로 초기화하고 시작
          
          if(left < this.heap.length && this.heap[left] < this.heap[min_index]) min_index = left
          if(right < this.heap.length && this.heap[right] < this.heap[min_index]) min_index = right
          
          if(min_index !== index){
              this.swap(min_index, index)
              this.bubbleDown(min_index)
          }
      }
      
  }
  
  function solution(scoville, K) {
      let count = 0
      
      let heap = new Heap()
      
      scoville.forEach((item) => heap.heappush(item))
      
      while(heap.heap[0] < K){
          if (heap.heap.length < 2) return -1; 
          
          let a = heap.heappop()
          let b = heap.heappop()
          let dish = a + b*2
          
          heap.heappush(dish)
          count++
      }
      
      return count
  }

✏️ 아하 모먼트 1

• shift 가 배열의 맨 앞 원소를 빼내는 거라면, unshift 는 배열의 맨 앞에 원소를 넣는 것

  

• splice 사용 방법

  splice(startIndex, deleteCount, item1, item2, ...itemN)

  // 예시
  let arr = [1, 2, 3, 4, 5];
  arr.splice(2, 2);  // 2번 인덱스부터 2개 삭제
  console.log(arr);  // [1, 2, 5]

• JavaScript 배열은 음수 인덱스를 직접 지원하지 않기 때문에 arr[-1] 같은 식의 접근은 불가능

• JavaScript에서는 PriorityQueue가 내장되어 있지 않아서 Min Heap (최소 힙) 을 직접 구현해야 함

• Heap : 우선순위 큐를 구현할 수 있는 완전 이진트리 기반의 자료구조

  • 언제 사용할까?
    • 우선순위가 있는 작업 (가장 작은, 가장 큰)
    • 매번 최소 or 최대 값을 뽑아야 하는 경우
    • 매번 push를 하는 경우 이유 : 원소 push 할 때 일반적인 배열에서는 O(N) vs Heap은 O(log N) 걸림
      

✏️ 아하 모먼트 2

• heap 자체는 완전 이진 트리를 기반으로 하는 자료구조이기 때문에 전체 힙이 정렬된 상태는 아님
  • heap을 크기 순서대로 정렬하려면 heap 정렬을 하면 됨 (heap 정렬 ≠ heap)
  • 힙 정렬은 O(N log N) 시간 복잡도를 가짐
  • 힙은 O(log N) 시간 복잡도를 가짐
• 최소 힙(min heap)에서는 맨 첫 번째 원소는 가장 작은 값임을 보장함
• 더 맵게 문제 유형은 ?
  • 힙 정렬 ❌ 아니고 heap을 이용한 우선순위큐 ⭕️

🔥 난이도

2025-02-03 기준 : 상 (시간초과 이슈를 해결하려면 꼭 Heap을 이해해야만 했고.. 사용해야만 했고.. JS에는 우선순위큐가 내장되어있지 않았고.. heap은 어렵고.. 정확히 이해한건지도 모르겠고.. 🤮)