문제 설명
회사원 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 |
효율성 통과 못한 풀이
function solution(n, works) {
if(works.reduce((a,b)=>a+b,0)<n) return 0
while(n>0){
n--
works.sort((a,b)=>b-a)
works[0]--
}
return works.map((v)=>v**2).reduce((a,b)=>a+b,0)
}배열의 각 숫자의 제곱을 합한 값이 가장 작으려면 각 숫자들의 편차가 가장 적게 만들어야 해서 가장 큰 값을 없애주는 방식을 생각했다.
n이 0보다 큰 동안 계속 works배열을 내림차순 정렬해주며 최댓값인 인덱스 0의 값을 하나씩 줄여주는 방식으로 풀었더니 테스트케이스는 모두 통과했지만 효율성 통과하지 못했다.
매 반복마다 sort를 해주는게 비효율적이기도 하고 저 sort때문에 효율성 통과를 하지 못하는 것 같아 더 효율적으로 최댓값을 제거해줘야 했다.
나의 최종 풀이
function solution(n, works) {
if (works.reduce((a, b) => a + b, 0) < n) return 0;
const sortedArr = works.sort((a, b) => b - a);
while (n) {
let max = sortedArr[0];
for (let i = 0; i < works.length; i++) {
if (sortedArr[i] >= max) {
sortedArr[i]--;
n--;
}
if (n == 0) break;
}
}
return sortedArr.map((v) => v ** 2).reduce((a, b) => a + b, 0);
}풀이 전략
1. 남은 시간 n보다 작업량을 모두 합한 값이 더 작으면 야근을 하지 않아도 되므로 빠르게 0을 return 해준다.
2. works 배열을 내림차순 정렬해준 후 n>0인 동안 반복해서 정렬한 sortedArr배열을 순회하며 max보다 크거나 같을 경우 해당 값과 n을 1씩 빼준다.
3. n이 0과 같아졌다면 배열 순회를 멈추고 while문을 빠져나온다.
4. sortedArr 배열의 각 값을 제곱한 후 합한 값을 return
review)
문제 자체는 어렵지 않았지만 효율성을 생각해서 푸는게 관건이었다. 효율성이 엄격하게 걸려있던 문제라 테스트케이스 통과까지는 빠르게 했지만 그 이후가 시간이 좀 걸렸다ㅠㅠ
효율성을 먼저 생각하고 풀어야할지 풀어놓고 효율성에 통과하지 못했다면 그 이후에 더 효율적인 방법으로 고쳐야 할지 고민이 된다.