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

adultlee·2023년 6월 7일
0
post-custom-banner

문제 링크

프로그래머스 문제

풀이

처음 생각한 방법은 야근지수를 최소화 하기 위해서, 야근 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

}
post-custom-banner

0개의 댓글