더 맵게

구현

1. 강의시간에 작성한 MaxHeap을 변환하여 사용하였음

2. 가장 작은 두 원소(Left, Right)를 추출, 스코빌 계산하여 다시 추가

3. 최소 원소가 K를 넘어설때까지 (2) 반복

4. 테스트케이스 및 효율성 실패

코드

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

  push(value) {
    // 1. 배열 맨 끝 노드에 값을 추가
    this.heap.push(value);

    // 2. 추가한 배열의 인덱스와 부모 노드 인덱스 추출
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    // 3. 부모 노드 우선순위가 더 높을 때까지 추가된 노드를 올림 (부모와 교환)
    while (parentIndex !== 0 && this.heap[parentIndex] > value) {
      const temp = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    // 1. 루트 요소 반환을 위해 임시로 상수에 저장
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    // 2. 노드 인덱스 초기 설정
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;

    // 3. 하위 노드들의 우선순위가 더 낮을 경우 반복문 종료
    while (this.heap[currentIndex] > this.heap[leftIndex] || this.heap[currentIndex] > this.heap[rightIndex]) {
      // 4. 자식 노드 우선순위를 비교, 더 낮은 것과 현재 노드를 바꿔줌
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    return returnValue;
  }

  peek() {
    return this.heap[1];
  }

  size() {
    return this.heap.length-1;
  }
}

function solution(scoville, K) {
    let answer = 0;
    const heap = new MinHeap();
    scoville.forEach((el) => heap.push(el));

    while (heap.peek() < K && heap.size() > 2) {
        const left = heap.pop();
        const right = heap.pop();
        const newItem = left + right * 2;
        heap.push(newItem);
        answer++;
    }

    return heap.peek() >= K ? answer : -1;
}

해설

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];
  }
}

function solution(scoville, K) {
  const minHeap = new MinHeap();

  for (const sco of scoville) {
    minHeap.push(sco);
  }

  let mixedCount = 0;

  while (minHeap.size() >= 2 && minHeap.peek() < K) {
    const first = minHeap.pop();
    const second = minHeap.pop();
    const mixedScov = first + second * 2;
    minHeap.push(mixedScov);
    mixedCount++;
  }

  return minHeap.peek() >= K ? mixedCount : -1;
}