[Programmers]야근 지수/JS

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

접근방법

야근 피로도를 최소한 값을 리턴해야 하는 문제이다.

먼저 works 배열을 내림차순으로 정렬해주고 가장 큰값과 다음 값을 비교해서 차이만큼 빼줘야겠다고 생각했다.

빼준 다음 다시 정렬하는 반복문을 n이 0일때까지 반복하면 되겠다라고 생각하고 코드를 작성했다.

실패코드

function solution(n, works) {
    var answer = 0;
    works.sort(function(a,b) {    // 내림차순 정렬
        return b-a;
    });

    while(n > 0) {
        let dif = works[0]-works[1];    // 두 수의 차이를 구해줌
        if(dif > n){    // 두 수의 차이가 n의 값보다 크면 
            dif = n;    // 차이에 n을 넣어주고
            n = 0;    // n을 0으로 설정
        }
        if (dif == 0){    // 두 수의 차이가 0이면
            works[0] -= 1;    // 가장 큰 값에서 -1
            n--;
        } else {    // 두 수의 차이가 n보다 작고 0이 아닌 경우
            works[0] -= dif;    // 가장 큰 값에서 차이를 빼줌
            n -= dif;
        }

        works.sort(function(a,b) {    // 다시 내림차순 정렬
            return b-a;
        })
    }

    works.map((item)=>{        // works 배열의 값들을 제곱해서 더해줌
        if(item < 0) item = 0;
        answer += Math.pow(Number(item), 2);
    })
    return answer;
}

사실 작성하면서도 이렇게 풀어도 되나 싶었다..

while문 안에서의 정렬이 비효율적이라는 생각을 했지만 딱히 다른 방법이 생각나지 않았다ㅠㅠ

일단 제출해보자!

정확성 테스트는 모두 통과하지만 효율성에서 시간 초과가 나온다..

GPT에게 시간복잡도를 물어봤더니 O(n^2 log n).. 하하..

정확성 테스트만 통과하면 끝이 아니라는걸 다시 뼈져리게 느꼈다

결국 구글링해서 도움을 얻었당

정답코드

function solution(n, works) {
    var answer = 0;
    works.sort((a,b) => b-a);    // 내림차순 정렬

    while(n) {
        let max = works[0]; // 가장 큰 값
        for(let i=0;i<works.length;i++){
             if (works[i] >= max) {    // 가장 큰 값과 비교해서 같거나 크면
                works[i] -= 1;    // -1을 빼준다
                n -= 1;
             }
            if(!n) break;    //n이 0이 되면 종료
        }
    }

    works.map((item)=>{    
        if(item < 0) return;
        answer += Math.pow(Number(item), 2);
    })
    return answer;
}

max에 가장 큰 값인 works[0]을 저장해준다.

for 문을 돌면서 max보다 같거나 큰 값을 만나면 -1을 빼주고

다시 while 문을 돌면서 max 값을 갱신해준다.

-1 씩만 빼주기 때문에 works[0]에 가장 큰 값이 저장된다는 사실은 변함없다.

마음이 편안해지는 사진

느낀 점

이제 시간복잡도를 따져가며 문제를 풀어야겠다는 걸 느꼈다.

외면하고 싶었던 문제를 직면해서 이제 정말 할 때가 됐구나 싶다.

다음 블로그는 시간 복잡도에 대한 내용으로 찾아오겠습니다.

코테 준비 화이팅..!