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