문제 설명
works에 있는 작업량을 n만큼 뺄 수 있는데 빼고 난 후 각 작업량의 제곱을 더한 값이 야근 지수가 됩니다.
작업량을 뺄 때 최대치만 없앤다고 좋은게 아니고 작업량을 최대한 비슷하게 만들면 야근 지수를 최소화 할 수 있습니다.
예를들어 [4,3,3]의 작업이 있을 때 4의 작업을 할 수 있다고 [3,3]을 만들면 3^2 + 3^2 = 18입니다.
하지만 최대값의 작업량을 없애면서 작업량을 비슷하게 만들면 [2,2,2]가 되고 2^2 + 2^2 + 2^2 = 12가 됩니다.
처음에는 모든 작업을 더하고 n 만큼 뺀 다음에 작업량을 골고루 분배해서 각 작업에 제곱을 하면 될줄 알았는데 테스트 케이스 에서 막혔습니다. 혹시나 이렇게 푸신 분은 알려주세요 ㅠ
다른 방법으로도 접근할 수 있는데
우선 순위 큐 자료구조를 생각하면 쉽게 접근 할 수 있습니다.
문제 풀이 절차
1. works배열을 내림차순으로 정렬합니다.
2. n만큼 반복
3. 배열의 맨 앞에 값이 제일 큰 값이기 때문에 -1을 해서 작업량을 빼줍니다.
4. 우선순위 대로 배열을 정렬합니다.( 작업량의 값이 높으면 우선순위 높습니다.)
ex. [3,3,2] 라고 했을 때 맨 앞의 값을 빼면 [2,3,2]가 되고 우선순위에 따라서 [3,2,2]로 정렬을 합니다.
이 과정을 반복합니다.
하지만
JS splice를 통해 어떤 값을 넣을 때는 그 공간을 만들기 위해 해당 위치의 값부터 한칸씩 뒤로 땡기는 연산이 수행됩니다.
예를들어 [1,2,3,4] 배열의 1번째 index에 5라는 값을 넣고 싶으면 공간을 만들기 위해 2,3,4는 한칸씩 뒤로 땡겨지고 해당 자리에 5라는 값이 들어가서 [1,5,2,3,4]가 됩니다.
즉 최대 O(n)만큼의 연산이 들어갑니다.
이를 최소화 하기 위해 큐를 뒤집어서 사용했습니다.
뒤집지 않으면 q.shift() q.splice()의 연산 비용이 많이 들기 때문에
뒤집어서 q.pop() q.splice()을 사용하여 연산 비용을 최소화 하였습니다.
실제로 푼 문제 풀이 절차
1. works배열을 오름차순으로 정렬 ex. [3,1,2] -> [1,2,3]
2. n만큼 반복
3. 배열의 맨 뒤에 값에 -1을 해서 작업량 빼줍니다.
4. 우선순위 대로 배열을 정렬
function solution(n, works) {
var answer = 0;
const lastIndex = works.length -1;
const sum = works.reduce( (acc, item) => acc+item, 0);
if ( (sum - n) <= 0 ) return 0;
// 오름차순
works.sort( (a,b) => a-b);
while( n !== 0 ){
works[lastIndex] -= 1;
n -= 1;
popAndAddToPQ(works);
}
answer = works.reduce( (acc, item) => acc + Math.pow(item, 2), 0);
return answer
}
function popAndAddToPQ(queue){
const item = queue.pop();
const length = queue.length;
for(let i = length-1; i >= 0; i--){
if( queue[i] <= item ) {
queue.splice(i+1, 0, item);
break;
}
}
if( length === queue.length ) queue.unshift(item);
}
