프로그래머스: 더 맵게 (Heap)

더 맵게

음식의 스코빌 지수가 담긴 배열 scoville이 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하기

제한 조건
2 ≤ scoville.length ≤ $10^6$

문제 풀이 조건
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 × 2)
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 하도록 함.

알고리즘 구상하기

시간복잡도를 줄이는데 집중한다.
모든 음식이 조건을 충족할 때까지 반복해서 음식을 섞어야 하므로, 음식의 수와 동일한 의미인 scoville의 길이가 중요하다.

scoville은 최대 $10^6$ 개의 요소를 갖기 때문에 이 문제는 시간복잡도를 고려하여 문제를 풀어야 한다.

적절한 자료구조: Heap(힙)
이 문제는 scoville 배열 요소 중 최솟값을 구하는 방법이 핵심이다.

scoville의 길이를 고려했을때, 단순히 새로운 스코빌 지수를 배열에 push할 때마다 Math.min() 메서드를 반복하거나 크기 순으로 정렬하는 방식은 비효율적이다.

실제로 나는 이번 문제를 풀기 전까지 Heap의 개념을 알지 못하여 위 방법들을 시도했고 효율성 문제로 인해 모두 실패했다.

결국 프로그래머스에서 이 문제의 유형을 Heap으로 분류했다는 사실에 힌트를 얻어 Heap에 대해 학습하였다.
그 결과, 다음의 이유로 이 문제가 Heap으로 풀기 적절하다는 점을 추론했다.

1. min-heap(최소 힙)으로 쉽게 최솟값을 파악할 수 있다.
   min-heap은 root node가 최솟값이 된다.

2. heap의 정렬은 시간복잡도가 항상 $O(nlogn)$으로 유지된다.
   heap 자료구조는 데이터들 간에 부모-자식 node 관계가 정립되며, 이는 우선순위 큐(Priority Queue)를 구현하는데 효율적이다.

   우선순위 큐는 FIFO 규칙을 따르는 일반적인 큐와 달리 최댓값, 최솟값과 같은 ‘우선순위’를 기준으로 데이터가 삭제되거나(out) 마지막에 놓이기 때문이다.

   이는 계속해서 root node인 최솟값을 빼내어 사용해야 하는 이 문제의 특성과도 결이 맞다.

이를 종합하여 Heap을 구현한 최종 결과는 다음과 같다.

[JavaScript]

class Heap {
  nodeList;

  constructor(arr) {
    this.nodeList = arr;
    this.makeHeap();
  }

  makeHeap() {
    for (let i = Math.floor(this.nodeList.length / 2) - 1; i >= 0; i--) {
      this.topDown(i);
    }
  }

  getSmallest() {
    if (this.nodeList.length === 0) {
      return null;
    }
    const rootNode = this.nodeList[0];
    const lastNode = this.nodeList.pop();

    if (this.nodeList.length > 0) {
      this.nodeList[0] = lastNode;
      this.topDown(0);
    }
    return rootNode;
  }

  bottomUp(currentNodeIndex) {
    while (currentNodeIndex > 0) {
      const parentNodeIndex = Math.floor((currentNodeIndex - 1) / 2);
      if (this.nodeList[parentNodeIndex] <= this.nodeList[currentNodeIndex])
        break;

      [this.nodeList[parentNodeIndex], this.nodeList[currentNodeIndex]] = [
        this.nodeList[currentNodeIndex],
        this.nodeList[parentNodeIndex],
      ];
      currentNodeIndex = parentNodeIndex;
    }
  }

  topDown(currentNodeIndex) {
    while (true) {
      let smallestNodeIndex = null;
      const leftChildNodeIndex = currentNodeIndex * 2 + 1;
      const rightChildNodeIndex = currentNodeIndex * 2 + 2;

      if (leftChildNodeIndex < this.nodeList.length) {
        smallestNodeIndex = leftChildNodeIndex;
      }

      if (
        rightChildNodeIndex < this.nodeList.length &&
        this.nodeList[rightChildNodeIndex] < this.nodeList[leftChildNodeIndex]
      ) {
        smallestNodeIndex = rightChildNodeIndex;
      }

      if (
        smallestNodeIndex === null ||
        this.nodeList[currentNodeIndex] <= this.nodeList[smallestNodeIndex]
      )
        break;

      [this.nodeList[currentNodeIndex], this.nodeList[smallestNodeIndex]] = [
        this.nodeList[smallestNodeIndex],
        this.nodeList[currentNodeIndex],
      ];
      currentNodeIndex = smallestNodeIndex;
    }
  }
}

function solution(scoville, K) {
  const heap = new Heap(scoville);
  let answer = 0;

  while (heap.nodeList.length > 1 && heap.nodeList[0] < K) {
    const smallest1 = heap.getSmallest();
    const smallest2 = heap.getSmallest();
    const newScoville = smallest1 + smallest2 * 2;
    heap.nodeList.push(newScoville);
    heap.bottomUp(heap.nodeList.length - 1);
    answer += 1;
  }

  return heap.nodeList[0] >= K ? answer : -1;
}

효율성 개선하기

사실 앞서 작성한 코드는 내가 처음에 구현한 코드가 아니었다.

나는 최종 코드와 달리, Heap을 Scoville 배열에 적용했을 때 scoville 지수들을 일일이 Heap 객체의 nodeList 배열에 Array.push하고 매번 정렬을 수행했었다.

그러나 이러한 방식은 nodeList에 새로운 요소가 들어올 때마다 다시 정렬하므로 비효율적이었다. 프로그래머스의 효율성 검사도 통과하지 못했다.

이를 개선하고자 매번 nodeList에 요소가 Array.push 될 때마다 정렬을 수행하지 않고 모든 요소가 nodeList에 들어왔을 때 한 번에 정렬하는 방향으로 바꾸었다.

이에 따라, makeHeap 라는 메서드를 새롭게 만들어 nodeList가 완성되면 모든 부모 노드를 대상으로 정렬을 수행하도록 하였다. 그리고 이 makeHeap 매서드를 생성자 함수에 넣어, Heap 인스턴스가 생성될 때 바로 호출되도록 했다.

기존 코드에서 매 Array.push마다 정렬하는 역할을 담당했던 Heap.push 메서드는 더 이상 사용하지 않으므로 삭제했다.

아래는 변화를 겪은 code line만 발췌한 것이다.

class Heap {
  nodeList;

  // makeHeap이 적용되지 않음.
  constructor() {
    this.nodeList = [];
  }

  // 매 Array.push마다 정렬을 수행했던 push 메서드. 코드 수정 후 제거됨. (makeHeap으로 대체)
  push(node) {
    this.nodeList.push(node);
    this.bottomUp(this.nodeList.length - 1);
  }
}

...

function solution(scoville, K) {
  const heap = new Heap();
  scoville.forEach((el) => heap.push(el)); // 비효율적인 로직
  let answer = 0;

  while (heap.nodeList.length > 1 && heap.nodeList[0] < K) {
    const smallest1 = heap.getSmallest();
    const smallest2 = heap.getSmallest();
    const newScoville = smallest1 + smallest2 * 2;
    heap.push(newScoville); // 비효율적인 로직
    answer += 1;
  }

  return heap.nodeList[0] >= K ? answer : -1;
}

Comment

Heap은 Priority Queue를 구현하기 위한 최적의 자료구조이다.

이번 문제를 풀면서 Heap과 Priority Queue(우선순위 큐)를 학습할 수 있었다.
특히 아래의 글이 많은 도움이 되었으며, Heap의 개념을 정립하는데 어려움을 겪고 있다면 좋은 참고가 될 것 같다.

Priority Queue 참고