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

풀이 과정

1. 무한 반복
2. 배열의 모든 원소가 K 이상이면 반복문 결과 리턴
3. 배열을 내림차순 정렬
4. 가장 뒤의 두 음식을 섞고 섞은 횟수 +1: pop()
5. 결과가 처음 배열의 길이와 같아지면 만들 수 없는 경우이므로 반복문 탈출

👉 효율성 테스트 통과 못함

🤔

제한 사항의 수가 너무 커서 걱정은 했지만 역시나...
힌트를 보니 힙을 꼭 사용해야 하는 문제라고 한다.
JS sort() 메소드가 내가 만드는 것보다 최적화가 잘 되어 있을 거라고 생각했는데 아니었나 보다.
sort()는 O(nlogn), 최소힙은 O(logn)이란다.
무튼 힙이라는 자료 구조가 JS에서 지원이 되지 않기 때문에 직접 구현을 해야 한다.

• 힙은 완전이진트리 규칙을 따름
• 최소힙은 루트가 가장 작고, 자식은 부모보다 크기만 하면 됨
• 왼쪽 자식의 인덱스는 부모 인덱스 * 2 + 1, 오른쪽 자식의 인덱스는 부모 인덱스 * 2 + 2
• 삽입: 새로운 노드를 마지막에 넣고 자기보다 부모가 작으면 자리 바꾸기
• 삭제: 루트 노드를 꺼내고 마지막에 있던 노드를 루트 자리에 넣은 후 자기보다 큰 자식이 있으면 자리 바꾸기

아래 블로그 글을 참고해서 공부했다.
https://reakwon.tistory.com/42
https://chamdom.blog/heap-using-js/

코드

function solution(scoville, K) {
  const heap = new MinHeap();
  for (const e of scoville) {
    heap.push(e);
  }

  let result = 0;
  while (heap.size() > 1 && heap.peek() < K) {
    const min1 = heap.pop();
    const min2 = heap.pop();
    heap.push(min1 + min2 * 2);
    ++result;
  }

  return heap.peek() < K ? -1 : result;
}

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

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

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

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  push(v) {
    this.heap.push(v);
    let i = this.size() - 1;
    let parentI = Math.floor((i - 1) / 2);
    while (i > 0 && this.heap[i] < this.heap[parentI]) {
      this.swap(i, parentI);
      i = parentI;
      parentI = Math.floor((i - 1) / 2);
    }
  }

  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) return this.heap.pop();

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

    let i = 0;
    while (i < this.size()) {
      const leftI = i * 2 + 1;
      const rightI = i * 2 + 2;
      let small = leftI;
      if (rightI < this.size() && this.heap[leftI] > this.heap[rightI]) {
        small = rightI;
      }
      if (this.heap[small] < this.heap[i]) {
        this.swap(small, i);
      }
      i = small;
    }

    return minV;
  }
}