[프로그래머스] 더 맵게 - JS

문제

풀이

나의 첫 풀이다.

function solution(scoville, K) {
    let answer = 0;
    scoville.sort((a, b) => a - b)
    while(scoville[0] < K){
        if(scoville.length <= 1){
            return -1
        }
        let newScoville = scoville.slice(2);
        newScoville.push(scoville[0] + scoville[1] * 2);
        scoville = newScoville.sort((a, b) => a - b);
        answer++;
    }
    return answer;
}

방법은 틀리지 않았지만, 효율성 테스트를 통과하지 못했다.
다른사람의 풀이를 참고하여 문제를 해결했다.
힙(heap)을 이용해 해결한 듯 하다.
JS에서는 힙을 직접 구현해야해서 어려운 것 같다.

// MinHeap 클래스를 정의하여 힙 연산을 캡슐화합니다.
class MinHeap {
  constructor() {
    this.heap = []; // 힙을 나타내는 빈 배열을 초기화합니다.
  }

  // 힙의 크기를 반환하는 메서드
  size() {
    return this.heap.length;
  }

  // 새로운 값을 힙에 삽입하는 메서드
  push(value) {
    this.heap.push(value); // 값을 배열에 추가합니다.
    let currentIndex = this.heap.length - 1;

    // 부모 노드와 비교하면서 힙 속성을 유지합니다.
    while (
      currentIndex > 0 &&
      this.heap[currentIndex] < this.heap[Math.floor((currentIndex - 1) / 2)]
    ) {
      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[Math.floor((currentIndex - 1) / 2)];
      this.heap[Math.floor((currentIndex - 1) / 2)] = temp;
      currentIndex = Math.floor((currentIndex - 1) / 2);
    }
  }

  // 힙에서 최솟값을 제거하고 반환하는 메서드
  pop() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    let currentIndex = 0;

    // 자식 노드와 비교하면서 힙 속성을 유지합니다.
    while (currentIndex * 2 + 1 < this.heap.length) {
      let minChildIndex =
        currentIndex * 2 + 2 < this.heap.length &&
        this.heap[currentIndex * 2 + 2] < this.heap[currentIndex * 2 + 1]
          ? currentIndex * 2 + 2
          : currentIndex * 2 + 1;

      if (this.heap[currentIndex] < this.heap[minChildIndex]) {
        break;
      }

      const temp = this.heap[currentIndex];
      this.heap[currentIndex] = this.heap[minChildIndex];
      this.heap[minChildIndex] = temp;
      currentIndex = minChildIndex;
    }

    return minValue;
  }

  // 힙에서 최솟값을 반환하는 메서드
  peek() {
    return this.heap[0];
  }
}

// 주어진 스코빌 배열과 K 값을 사용하여 문제를 해결하는 함수
function solution(scoville, K) {
  const minHeap = new MinHeap(); // MinHeap 클래스의 인스턴스 생성

  // 주어진 스코빌 값을 힙에 추가
  for (const sco of scoville) {
    minHeap.push(sco);
  }

  let mixedCount = 0; // 섞은 횟수를 초기화

  // 힙의 크기가 2 이상이고 최솟값이 K 미만인 경우 반복
  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    const first = minHeap.pop(); // 가장 작은 값
    const second = minHeap.pop(); // 두 번째로 작은 값
    const mixedScov = first + second * 2; // 새로운 값 계산
    minHeap.push(mixedScov); // 새로운 값 힙에 추가
    mixedCount++; // 섞은 횟수 증가
  }

  // 힙의 최솟값이 K 이상인지 확인하여 결과 반환
  return minHeap.peek() >= K ? mixedCount : -1;
}