문제 링크

프로그래머스 문제

풀이

처음 생각한 방법은 야근지수를 최소화 하기 위해서, 야근 1시간 수행 할때마다 전체 시간에서 한시간씩 줄여가면서 매번 정렬을 다시 수행해 주었습니다.
하지만 이경우 시간초과가 발생했으며, 여기서 시간을 더 줄일 수 있는 방법이 필요함을 알게 되었습니다.
그래서 생각해본 결과, 불가피하게 굳이 마지막 지점에서 제거하는 것이 아닌 한번의 탐색에서 줄일 수 있는 모든 요소를 줄이는 것이 필요하다고 생각하게 되었습니다.

for(let i=0; i< works.length; i++){
            if(max === works[i]){
                works[i] -=1;
                n--;
            }
            if(n===0) break;
}

위의 코드가 해당 문제에서 가장 중요한 부분이었습니다.
다음의 방식은, 현재 시간이 많은 지점에서 1시간을 줄이고 다시 while문을 반복하는 것이 아닌,

중복된 연산과정을 획기적으로 줄일 수 있습니다.
예를 들어 다음과 같은 시간들을 가지고 있을때,

[ 4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5 ,... ,5]

한시간을 제거 하게 된다면,

[4,4,4,4, 5,5,5,5,5,5,5,5,5,5,5 .... ,4]
위와 같이 되며 다시 정렬을 진행해야 하며
[4,4,4,4,4, 5,5,5,5,5,5,5,5,5, ... 5]
가 만들어지게 됩니다.

하지만 위의 for문을 추가하게 된다면

[4,4,4,4,4 , ... 4 , 5, 5,5,5 .... 5]
로 바로 진행할 수 있게 됩니다. max값 과 같은 지점에서는 미리 n이 줄어드는 것을 제어할 수 있기 때문입니다.

코드

function solution(n, works) {
    var answer = 0;
    while(n){
        works.sort((a,b) => a-b)
        const max = works[works.length-1]

        for(let i=0; i< works.length; i++){
            if(max === works[i]){
                works[i] -=1;
                n--;
            }
            if(n===0) break;
        }


    }

    works.map( v => {
        if(v >=0)
        answer+= v*v
        else return 0
    })
    return answer

}