[프로그래머스] Lv3. 야근 지수- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 야근 지수

문제

제한사항

📌 내가 생각한 풀이

Max를 고정시키고, Max보다 크거나 같은 값을 빼주자. sort를 계속 할 필요없이, Max보다 큰 값들은 하나씩 자동으로 빠진다.

function solution(n, works) {
    var answer = 0;
    let table = {};
    works.sort((a,b)=>b-a);
    while(n != 0){
        let max = works[0];
        for(var i = 0; i<works.length; i++){
            if(works[i] >= max){
                works[i]--;
                n--;
            }
            if(n ==0){
                break;
            }
        }

    }
    works.filter((data)=>data >= 0).map((d)=>{
        answer += Math.pow(d,2)
    })
    return answer;
}

📌 느낀점

최대값을 찾기위해 Sort를 계속하면, 시간복잡도 면에서 매우 비효율적이였다. 다르게 생각해보면, 내림차순으로 정렬한 works에서 처음 실행할 때works[0]가 max인것은 당연하고, 이보다 큰거나 같은 값 이 있으면 빼주면 결국 works[0]은 항상 max임이 된다. sort를 계속 하지않고도, 최대값을 찾는 방법을 알게되었다.