[JS] Heap - 배상 비용 최소화

https://programmers.co.kr/learn/courses/13213/lessons/91086

프로그래머스

 

 

문제 유형 파악하기

문제 설명 중 핵심 부분은 배상 비용을 계산하는 부분이다. 배상 비용은 각 요소를 제곱하게 되므로 최대한 각 요소를 골고루 처리하는 것이 배상 비용을 가장 최소화 할 수 있는 방법이다.

그러기 위해서는 매 루프마다 가장 큰 작업을 찾아서 처리해야 한다. 이때 가장 큰 작업을 찾기 위한 방법은 3가지가 있다.

1. 매 루프마다 Math.max 함수를 호출한다.
2. 매 루프마다 정렬한다.
3. Heap을 이용한다.

1번은 매 루프마다 O(n) 시간복잡도가 소요된다. 2번은 O(n log n)이 소요된다. 반면 Heap을 이용하면 O(log n)만이 소요된다.

사실 매번 큰 값 혹은 작은 값을 알아야 한다면 무조건 Heap을 사용하는 것이 좋다.

 

 

최대 힙 구현

가장 큰 값을 알기 위해선 최대 힙을 구현해야 한다.

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

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    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() {
    if (this.heap.length === 2) return this.heap.pop(); // 루트 정점만 남은 경우

    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currentIndex  = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (this.heap[currentIndex] < this.heap[leftIndex] || 
        this.heap[currentIndex] < this.heap[rightIndex]) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }

    return returnValue;
  }
}

 

 

solution 함수 구현

function solution(no, works) {
  // 모든 작업의 합보다 no가 크면 배상 비용을 낼 필요가 없다.
  if (works.reduce((a, b) => a + b) <= no) { 
      return 0;
  }

  // max heap 구성
  const heap = new MaxHeap();
  for (const work of works) {
      heap.push(work);
  }

  // no만큼 루프 돌면서 가장 큰 값을 빼서 처리 후 다시 push
  for (let i = 0; i < no; i += 1) {
      heap.push(heap.pop() - 1);
  }

  // 남은 요소에 제곱한 값들의 합을 구한 후 반환
  return heap.heap.reduce((a, b) => a + b * b);
}