[프로그래머스 lev3/JS] 야근 지수

문제 출처

프로그래머스 lev3 - 야근 지수

나의 풀이

1차시도 (런타임에러)

길이가 너무 길어서 재귀를 돌지 못하는 경우가 발생한다.
(반례 : console.log(solution(999, [800, 100, 55, 45])) // 1)

중복 순열로 경우의수를 전부 구하려고 하면
RangeError: Maximum call stack size exceeded가 발생한다.

const getPermutations = (arr, selectNum) => {
  const results = [];
  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index, origin) => {
    const permutations = getPermutations(origin, selectNum - 1);
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });

  
  return results; 
};

function solution(n, works) {
  let start = works.reduce((a,b) => a+b, 0)
  if (n > start) return 0

  let answer = Number.MAX_SAFE_INTEGER
  const numArr = [...Array(n+1).keys()]
  // 중복 순열
  const list = getPermutations(numArr, works.length)

  list.map(arr => {
    const sum = arr.reduce((a,b) => a+b, 0)
    if(sum === n) {
      let res = 0
      for(let i=0; i<arr.length; i++){
        res += (works[i]-arr[i])**2
      }
      answer = Math.min(answer, res)
    }
  })

  return answer
}

console.log(solution(4, [4, 3, 3]))
console.log(solution(1, [2, 1, 2]))
console.log(solution(3, [1, 1]))

다른 풀이

그리디

제곱한 요소들의 합이 최소값이 되려면 큰 수를 최대한 없애야 한다.

이때 배열 중 가장 큰 값을 가진 요소를 한번에 제거해버리는 게 아니라,
요소 중 가장 큰 값에서 1만 빼준다.

왜냐하면 1을 빼줬을 때, 요소 중 큰 값이 달라질 수 있기 때문이다.
(예를 들어, 배열 [999, 999, ...]에서 가장 큰 값은 배열[0]의 999인데 여기서 1을 빼주면 최대값은 [0]이 아니라 [1]로 바뀔 수 있다)

while문을 돌면서 최대값인 원소에서 1을 빼주면 되는데,

while(n) {
  n--;
  sorted[len-1]--;
  sorted = sorted.sort((a, b) => a-b);
}

단순히 위처럼 매번 sort를 통해 최대값을 계산하면 효율성이 떨어진다.
(매번 모든 요소를 순회해야 하므로 모든 while문마다 단순히 정렬을 위해 매번 for문을 돌아야 하므로 O(N)이 제곱된다.)

애초에 1만 빼주는 이유는 요소 내에 같은 값을 가진 최대값이 있는 경우를 대비하기 위함이다. 그러므로 while 문에서 for문을 한번 더 순회하면서 최대값을 유지하는 방법을 찾아야 한다. (이때의 for문은 단순히 정렬을 위한 반복이 아니라 값을 찾기 위한 반복이므로 시간복잡도를 확연하게 개선할 수 있다.)

for문으로 요소를 한번 더 순회해서 최대값이 뒤에 또 있으면 1을 빼주는 식으로 하면, sort를 사용하지 않아도 항상 마지막 요소를 최대값으로 유지할 수 있다.

function solution(n, works) {
  if(works.reduce((a,b) => a+b) <= n) return 0;
  
  let sorted = works.sort((a,b) => a-b);
  const len = works.length;
  
  while(n) {
    const max = sorted[len-1];
    
    for(let i = len-1; i >= 0; i--) {
      if(sorted[i] >= max) {
        sorted[i]--;
        n--;
      }
      if(!n) break;
    }
  }
  
  return sorted.reduce((a,b) => a + Math.pow(b, 2), 0);
}

참고

[프로그래머스] LV.3 야근 지수 (JS)