[프로그래머스][LEVEL3] 야근지수

# 문제 원문

회사원 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

# 문제 풀이

입력 받은 works에서 n만큼 수를 빼서 평균이 가장 적은 숫자 배열을 얻는 문제이다. 먼저 입력받은 works 배열을 오름차순 또는 내림차순으로 정렬한다. 그 후 입력 받은 n 만큼 반복하면서 works의 가장 큰 수를 1씩 빼주면 되는데 단순히 가장 큰수를 매순간 찾아서 빼낼 경우 그것을 탐색하는 비용이 커서 추가적으로 있는 효율성 테스트 케이스 2건을 통과하지 못한다. (개정 전에는 효율성 케이스가 없었던 것으로 보인다.) 가장 큰수를 매순간 찾거나 매순간 배열을 정렬한 방법으로는 정확성은 통과 할 수 있지만 효율성을 통과하지 못하므로 우선순위 큐 같은 가장 큰수를 찾는 비용을 줄일 방법을 고려 할 필요가 있다. 그러나, JS에서는 우선순위 큐를 자료구조로 제공해주지 않으므로 굳이 우선순위 큐를 구현하지는 않았고, 나는 그냥 정렬된 배열을 순회하면서 가장 큰 수 보다 큰 수들을 모두 1씩 제하는 방법으로 탐색에 드는 비용을 없앴다. 추가적으로 규칙이 있나해서 찾아본 바로는 works의 토탈과 -n의 총합을 구한후 다시 works.length 만큼의 배열로 나누는 방법이 있을거 같긴 하지만 경우의 수가 많아서 실제로 구현하기에는 귀찮아서 그만뒀다.

# 솔루션 플로우

1. 입력 받은 works를 정렬한 배열 result를 구한다.

2. 입력 받은 n 즉 time이 0 이될때 까지 반복한다.

3. result의 가장 큰 수부터 result[idx]이 result[idx + 1]보다 크거나 같을때까지 1씩 제해준다.(time,result[idx])

4. time이 0이 될때까지 반복해준후 얻어진 result를 순회하면서 각요소의 제곱의 합을 구한다.

5. 얻어진 result를 반환한다.

1. 반복문을 활용한 풀이

function solution(n, works) {
    const result = Array.from(works).sort((a, b) => b - a);

    let time = n;
    while (time > 0) {
        for (let idx = 0; idx < result.length; idx++) {
            result[idx]--;
            time--;
            if (result[idx] >= result[idx + 1] || time <= 0) break;
        }
    }

    return result.reduce((result, current) =>
        current > 0 ?
            result += (current ** 2) :
            result
        , 0);
}