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

KG·2021년 4월 15일

알고리즘

목록 보기

19/61

문제

회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.

제한

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

입출력 예시

works	n	result
[4, 3, 3]	4	12
[2, 1, 2]	1	6
[1,1]	3	0

풀이

그리디(Greedy)한 방법으로 풀 수 있는 문제이다. 문제에서 요구하는 것은 야근 피로도의 최소값이다. 가장 단순하게 최소값을 만들 수 있는 방법을 생각해보자.

피로도의 최솟값은 근무시간을 모두 마치고 남은 상태에서 각 남은 작업들의 제곱의 합으로 구한다. 제곱이라는 것을 잘 생각해보자. 간단하고 극단적인 예로 현재 works의 값이 [4, 2, 2, 2, 2, 2, 2, ...] 라고 가정해보자.

이 상태에서 바로 근무 피로도를 계산한다면 각 원소의 제곱의 합은 16 + 4 + 4 + 4 + 4 + 4 + ... 이 될 것이다. 상식적으로 나보다 큰 수의 제곱수는 항상 나의 제곱수보다 크다는 것을 알 수 있다. 즉 최솟값의 합을 만들기 위해서는 큰 수를 최대한 없애야 할 것이다. 따라서 우리는 주어진 works의 원소 중에서 제일 큰 값을 우선적으로 1만큼 빼줄 것이다. 이때 가장 큰 값을 1만큼 빼주고난 후에 해당 배열에서 가장 큰 값이 바뀔 수 있다. 따라서 가장 큰 값을 다시 찾아서 해당 값을 우선적으로 빼주어야 할 것이다. 이는 다음과 같이 정렬을 이용하여 쉽게 해결할 수 있다.

// 현재 works를 오름차순 정렬한다.
// 마지막 위치에 가장 큰 값이 배치될 것이다.
let sorted = works.sort((a, b) => a-b);

그리고 주어진 n만큼 반복문을 돌자. 여기서는 while문을 이용해 반복을 돌지만 for문을 이용해도 상관은 없다. 해당 반복문 내부에서는 정렬된 배열의 마지막 원소값에 접근해 그 값을 1만큼 빼줄것이다. 이때 배열의 최댓값이 바뀔 수 있으므로 (동일한 값이 2개 이상 존재하는 경우) 다시 반복문을 돌기전에 해당 배열을 오름차순으로 재정렬 해주자.

const len = works.length;

while(n) {
  n--;	// n만큼 반복하기 위해 한 번의 반복마다 1식 빼준다.
  sorted[len-1]--;	// 마지막 원소가 최댓값이므로 1만큼 빼준다
  sorted = sorted.sort((a, b) => a-b);  // 다시 오름차순 정렬
}

그러나!! 이 경우엔 시간복잡도로 인해 효율성 테스트를 통과하지 못한다. n의 최대값이 백만이고 works의 최대 길이가 2만이기 때문에 최대 O(2백억)의 시간복잡도가 나올 수 있다. 그러면 위의 방식에 어떤 식의 최적화를 적용해야 한다. 위 구조를 최대한 망가뜨리지 않으면서 가지치기를 통해 시간복잡도를 줄여보도록 하자.

일단 sorted[len-1] 에 현재 최대값이 들어있다는 것은 자명하다. 우리가 while 문 내부에서 최댓값을 1만큼 빼준후 다시 오름차순 정렬을 한 이유는 현재 최댓값의 값이 감소하면서 다른 최댓값이 등장할 수 있기 때문이었다. 그리고 배열의 마지막 위치에 해당 최댓값을 위치시키기 위해 재정렬을 해주었다.

그런데 굳이 그때마다 최댓값을 하나씩 찾아 1씩 빼주고 다시 재정렬을 해 줄 필요가 있을까? 위 과정을 한 번에 실행할 수는 없을까? 다음을 생각해보자. 현재 오름차순으로 정렬된 배열의 마지막 값은 분명히 최댓값이다. 그런데 배열 내에는 이 최댓값과 동일한 값들이 존재할 수 있다. 그렇다면 우리는 굳이 이 값들을 하나씩 찾아서 제거하는 것이 아니라 현재 최댓값과 동일한 녀석들은 모두 한 번에 제거가 가능하다. 또한 이 구조를 가져가면 우리는 재정렬 없이 계속해서 최댓값을 배열의 마지막 위치에 유지시킬 수 있다. 나와 동일한 값을 가진 원소때문에 오름차순 정렬을 매 반복마다 해주었는데, 동일값을 모두 한 번에 제거해준다면 그럴 필요가 없기 때문이다.

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

그러면 우리는 그리디하게 최댓값을 그때마다 찾아 우선적으로 제거해주었기 때문에 해당 배열의 값들은 하향 평준화되었을 것이다. 따라서 이들의 제곱의 합이 최솟값이 될 것이다. 다음처럼 reduce를 이용해 제곱의 합을 구해주었다. 이때 입출력 예의 3번 처럼 주어진 작업보다 일하는 시간이 더 긴 경우엔 0을 리턴해야 한다. 하지만 지금의 경우엔 위 반복문에서 초과되는 시간은 마이너스 값으로 들어가고 마이너스값을 제곱하는 경우 양수가 되므로 0이 나올 수 없다. 따라서 works 배열의 총 합이 주어진 n 보다 작거나 같은 경우엔 0을 리턴하도록 조건부 처리해주자. (또는 sorted 배열에 마이너스 값이 들어가지 않도록 컨트롤 해주어도 된다)

// 처리해야할 총 작업량보다 근무시간이 같거나 크다면
// 모든 일을 처리할 수 있기에 피로도가 없다.
if(works.reduce((a,b) => a+b) <= n) return 0;

...

return works.reduce((a, b) => a + Math.pow(b, 2), 0);

다음은 주석을 제외한 전체코드이다. 꼭 이 방식이 아니라 최대힙(Max Heap; 자바의 경우 우선순위큐)을 이용해서도 풀이가 가능하다. 그러나 앞서 여기에서 언급한 것 처럼 JS는 힙을 일일이 구현해야 하며 그 양이 결코 적진 않다. 따라서 '나는 이 문제를 힙으로 풀어보겠다!' 하는 분들은 해당 포스트를 참고하여 직접 구현해보는 것을 추천한다!

코드

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