[Programmers Level 3] 야근지수 Javascript

⚡문제정보

 

제가 멍청해서 그런건진 몰라도 문제 설명이 너무 간략해서 이해가 안되었습니다.

생각을 해보면 야근지수는 제곱해서 계산하니까 최대한 값을 평탄화 시켜주는게 포인트인 문제입니다.

주어지는 매개변수 n만큼 works에서 시간을 뺄 수 있는구조인데

당연하지만 제곱을 하게되면 값이 기하급수적으로 커지니 주어진 자원으로 최대한

평탄화 작업을 해줘야하는 문제네요

 

예컨대 [4,3,3]이면서 내게 주어진 n이 4라면

4 -2 / 3-1 / 3-1을 해줘서 모든 값을 2로 맞춰주는게 최선일것입니다.

---

🔍접근방법

이거 뭐 쉽게 구현할 수 있지않나?하고 생각해봤는데

제가 쉽게 떠올릴 수 있는 방법들은 시간복잡도가 너무 커지는 방법들이었고..

검색을 살짝 해본 결과 이 문제는 3레벨 답게 빡빡한 효율성 테스트를 거치기때문에

알고리즘을 잘 선택해야한다는것을 알 수 있었습니다.

 

최대힙이나 우선순위 큐를 이용하면 쉽게 구할 수 있다는데

저는 그리디 알고리즘으로 문제를 푼 사람을 참고해서 그리디로 풀었습니다.

---

🔍좀 많이 참고한 나의 풀이

function solution(n, works) {
    if(n >= works.reduce((acc,cur) => acc + cur)) return 0;
    works.sort((a,b) => b-a)
    while(n != 0) {
        const max = works[0]
        for(i=0 ; i<works.length; i++) {
            if(works[i] >= max) {
                n--
                works[i]--
            }
            if(!n) break
        };
    };
    return works.reduce((acc,cur) => acc + cur**2 , 0 )
}

 

---

🔍이거 어떤 방식으로 동작하나요?

동작 방식은 다음과 같습니다.

sort를 내림차순으로 해주면 맨 앞 인덱스의 배열이 가장 큰 값일것입니다.

예컨대 [3,4,3]으로 배열이 주어졌다면 sort했을때는 [4,3,3]이 될것입니다.

 

그러면 max값을 맨앞 인덱스로 설정해주고

for문을 통해 max값이랑 같거나 크면 해당 원소의 값을 줄여줍니다.

이 과정에서 맨 앞 인덱스는 항상 값이 작아집니다.

맨앞인덱스는 항상 최댓값이니 뒷인덱스가 앞인덱스보다 값이 큰 일은 절대 일어나지않습니다.

 

[4,3,2] 라면 처음 루프때 [3,3,2]가 되고

두번째루프때 max값이 업데이트되면서 [2,2,2]가 되는식으로 평탄화되는거죠!

정말 똑똑하네요.. 전 생각도 못함

설명은 다음과 같습니다.

function solution(n, works) {
    if(n >= works.reduce((acc,cur) => acc + cur)) return 0;
    //n이 works의 총합과 같거나 더 크다면 어차피 모든 일을 할 수 있으니 야근지수는 0입니다.
    
    works.sort((a,b) => b-a)
    // works 배열의 원소를 내림차순으로 정렬합니다.
    
    while(n != 0) {
    //n이 0이될때까지 while문을 반복합니다.
    
        const max = works[0]
        //while문이 돌때마다 max값을 갱신해줍니다.
        
        for(i=0 ; i<works.length; i++) {
            if(works[i] >= max) {
                n--
                works[i]--
            }
            //만약 works[i]가 max값과 같거나 크면 n과 요소를 1씩 빼줍니다.
            
            if(!n) break
            // 위 if 케이스에서 n이 --되면서 n이 0이 되었다면 for문에서 탈출합니다.
        };
    };
    return works.reduce((acc,cur) => acc + cur**2 , 0 )
    // 각요소를 제곱한 값을 담아서 리턴합니다.
}