프로그래머스 [배상 비용 최소화]

제곱합을 최소로 만드는 문제

• 주어진 배열에서 매개 변수로 주어지는 n이 0이 될 때까지 작업량을 담고 있는 배열의 요소를 하나씩 감소시키고, 이 요소들의 제곱 합을 최소로 만드는 답을 반환하는 문제이다.

로직

배상 비용을 최소화한 값 반환하기

1. works 중 최대값을 일한시간 만큼 차감
2. n이 0이 될 때까지 1번 과정 반복
3. 위 반복이 모두 종료되면 works 내 제곱 합 반환

• 제곱의 합을 "최소"로 만들기 위해서는 가장 큰 수부터 감소시켜야한다. 따라서 배열 내 최대값을 계속 탐색하며 하나씩 감소시키고, 배열의 요소들의 제곱 합을 구하면 해결 가능한 문제이다.

작성한 코드

function solution(no, works) {
    let answer = 0

    while(no > 0) {
        const index = works.findIndex(el => el === Math.max(...works))
        if(works[index] <= 0) break; <= 테스트 케이스 7, 8
        works[index] -= 1
        no -= 1
   }
    
   for(let i in works) {
       answer = answer + (works[i] * works[i])
   }
    
    return answer
}

while 내 if 문은 추후에 추가한 코드이다. if 문 없이 채점을 돌려봤더니 테스트 케이스 7, 8번이 통과되지 않았었다. 이유를 생각해보니, 모든 요소가 0이 되고도 작업 가능한 시간이 남아있다면, 계속해서 작업량을 차감시키게 되어 작업량은 음수가 된다. 음수가 된 작업량을 제곱하면 양수가 되기 때문에 배상 비용을 최소화 시키지 못하게 된다. 따라서 작업량들의 최대값이 0이라면(즉 모든 작업량이 0이 되었다면) 반복을 중지시켜야 한다.

효율성 테스트 불합격

• 기본적인 테스트 케이스들을 모두 통과하는데 성공했지만, 효율성 테스트 2가지 모두 통과하지 못했다.

시간복잡도

• 매 루프마다 Math.max 함수를 호출하기 때문에 O(n)의 시간복잡도를 가진다.
• 주어진 문제는 최대값을 찾아야하는 문제이기 때문에 "힙"을 이용하는게 시간복잡도 면에서 효율적이다.
  • 힙은 O(logn)의 시간복잡도를 가진다.

최대 힙 구현

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

구현한 최대 힙을 이용한 풀이

function solution(no, works) {
    // 모든 작업량의 합이 작업 가능한 시간보다 작거나 같으면, 
    // 배상가능한 비용은 무조건 0이 되어 계산할 필요가 없음
    if(works.reduce((a, b) => a + b) <= no) return 0
    // 최대 힙 생성
   const heap = new MaxHeap()
   
   // 최대 힙에 주어진 works의 값들 삽입
   for(let work in works) {
       heap.push(works[work])
   }
    
    // no 만큼 for loop을 돌면서 작업량 1씩 차감
    for(let i = 0; i < no; i++) {
        heap.push(heap.pop() - 1)
    }
    return heap.heap.reduce((a, b) => a + b * b)
}