[Javascript] 프로그래머스 - 야근 지수

문제 설명

하나의 작업은 1시간에 1만큼 처리할 수 있으며, 퇴근까지 남은 시간 N시간 동안 일의 작업량을 분배하여 남은 일의 작업량의 제곱 합(야근 피로도)을 최소화해야 합니다. 작업량이 클수록 야근 피로도에 더 큰 영향을 주기 때문에, 가장 큰 작업량부터 줄이는 방식이 효율적입니다.

제한 사항

• works는 길이 1 이상, 20,000 이하인 배열입니다.
• works의 원소는 50,000 이하인 자연수입니다.
• n은 1,000,000 이하인 자연수입니다.

해결 방법

알고리즘: 우선순위 큐 (Max Heap)

가장 많은 작업량부터 줄이기 위해 최대 힙을 사용합니다.

1. 모든 작업량을 최대 힙에 삽입합니다.
2. 남은 시간이 있는 동안, 가장 큰 작업량을 꺼내 1만큼 줄인 뒤 다시 힙에 삽입합니다.
3. 작업량이 0 이하가 되더라도 힙에 삽입하며, 이후 정답 계산 시 0 이하 작업량은 0으로 처리합니다.
4. 모든 작업량을 꺼내 제곱한 값을 누적하여 반환합니다.

시간 복잡도

• 최대 힙 삽입 및 제거 연산: O(log N)
• 최대 N번의 연산을 하므로 전체 시간 복잡도는 O(N log W), 여기서 W는 works의 길이입니다.

구현 코드

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

  push(value) {
    this.heap.push(value);
    let i = this.heap.length - 1;
    while (i > 0) {
      let p = Math.floor((i - 1) / 2);
      if (this.heap[p] >= this.heap[i]) break;
      [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
      i = p;
    }
  }

  pop() {
    if (this.heap.length === 0) return 0;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length === 0) return top;
    this.heap[0] = last;
    let i = 0;
    const n = this.heap.length;
    while (true) {
      let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
      if (left < n && this.heap[left] > this.heap[largest]) largest = left;
      if (right < n && this.heap[right] > this.heap[largest]) largest = right;
      if (largest === i) break;
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
    return top;
  }
}

function solution(n, works) {
  let answer = 0;
  const pq = new MaxHeap();

  for (const work of works) {
    pq.push(work);
  }

  while (n > 0) {
    let work = pq.pop();

    --work;
    --n;
    pq.push(work);
  }

  while (pq.heap.length > 0) {
    const work = pq.pop();

    answer += work <= 0 ? 0 : work ** 2;
  }

  return answer;
}