[programmers] 야근 지수

Programmers Lv.3 야근 지수

순서가 좀 바뀌었긴 한데, JavaScript로 풀었던 마지막 문제이다.
파이썬으로 다시 풀어볼까 고민하였으나 굳이 그럴 필요는 없을 것 같다.

function solution(n, works) {
    var answer = 0;
    if(works.reduce((a,b) => a+b) <= n){
        return 0; // 시간 안에 일 다 할수 있으면 야근X
    }
    works.sort((a,b) => b-a);
    var maxwork = works[0];
    while(n>0){
        if(maxwork == 0){
            return 0;
        }
        // 논리를 세워보자.
        // works를 조사해서 maxwork랑 같으면 빼야함.
        // 전부다 maxwork랑 같은게 없으면 maxwork를 1빼야함.
        for(i=0; i<works.length; i++){
            if(works[i] !== maxwork || n == 0){
                // 남은 업무시간이 없으면 관둬야하고,
                // 다 찾았는데 maxwork와 같은 게 없으면 maxwork -= 1 하고 다시 while문
            }
            else{ // 아니면 works[i]를 1빼고 업무시간도 1빼야함.
                works[i] -= 1;
                n -= 1;
            }
        }
        maxwork -= 1; // 없으면 maxwork를 1 내려서 다시 탐색
    }
    for(i=0; i<works.length; i++){
        answer += works[i] ** 2;
    }
        
    return answer;
}

이 문제는 논리 자체는 간단하지만, 효율성 테스트가 골치아팠다.
처음 풀때는 매 동작마다 sorting을 하여 문제를 풀었는데,
아무래도 시간복잡도가 나쁜 작업이다 보니.. 시간초과가 계속 떴다.

핵심 아이디어는 sort 작업을 최소화 하는 전략을 세우는 것이다.
sort를 처음 한 번만 하고, 이후에는 단순 연산을 통해 복잡도를 줄였다.

아직까지는 단순히 내 풀이를 올리는 정도에 그치고 있다.
아무래도 아직 문제 난이도가 높지 않다보니..

앞으로는 내 풀이에서 개선하면 좋을 점이나,
다른 사람의 참조할만한 코드도 같이 작성하여
배울만한 포인트를 적으면 더 좋지 않을까 생각이 든다.