프로그래머스) 야근지수 (js)

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

최초에 푼 코드는 아래와 같다.

function solution(n, arr) {
    var answer = 0;
    
    while (n > 0){
        arr = arr.sort((a, b) => b - a); // (1)
        arr[0] -= 1;
        n--;
        
        if(arr[0] < 0) return 0;
    }
    
    answer = arr.reduce((pre, curr) => {
        pre += curr * curr;
        return pre;
    },0);
    
    return answer;
}

문제의 요구에 따라 직관적으로 짠 코드이다. 제시된 n 을 배열 내 가장 큰 수들에게 고르게 빼서 최대한 비슷한 값으로 만들면
최소값이 될 것이므로 위와같은 코드를 완성하였다. 그런데

시간초과

n 이 1,000,000 까지이고 work배열이 20,000길이 까지 될 수 있는데, 위 로직에서는 매 루프마다 최대값을 구하기 때문에
1,000,000 * 20,000 만큼의 복잡도를 갖게된다. 그래서 매번 최대값을 구하면 안될 것으로 판단하였다.

수정하여 제출한 코드는 아래와 같다.

function solution(n, arr) {
    var answer = 0;
    
    if(arr.reduce((acc, curr) => acc + curr, 0) <= n) return 0;
    
    arr = arr.sort((a, b) => a - b);
    while (n > 0){
        let max = arr[arr.length - 1];
        for(let i = arr.length - 1; i >=0 ;i--){ // (1)
            if(max <= arr[i]){
                arr[i]--;
                n --;
            }
            if(n === 0) break;
        }
    }
    
    answer = arr.reduce((pre, curr) => {
        pre += curr * curr;
        return pre;
    },0);
    
    return answer;
}

오름차순으로 정렬한 배열을 뒤부터 순회하는데 ( (1) ), 배열의 끝값과 같은값들(최대값)만 -1을 하는 식으로 주어진 n만큼 계속 -1한다.
이렇게 하면 배열의 최대값을 매번 구하지 않아도 배열의 맨 마지막 값들이 최대값이 된다.
따라서 매번 배열의 최대값을 구하지 않으면서 정답을 구하기 때문에 속도측면에서 더 유리할 것이다.

다행히 통과.