프로그래머스: 야근 지수 [JAVA]

문제 링크

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

코딩테스트 연습 - 야근 지수

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 works 배열을 오름차순으로 정리한 다음, 최소 작업량 기준으로 이후 작업들에 대해 차이를 더해 누적 계산 (추가로 작업량의 총합도 계산)
   
2. 이후 반복문을 통해 최소값 기준 차이나는 작업들의 누적합(diffWorkSum)이 소화 작업량(n)보다 작을 때까지 기준 최소값을 높임
3. 추가로 (diffWorkSum - n )을 적용가능 개수(works.length - 기준 최소값 인덱스)로 나눠 기준 최소값보다 얼마를 뺄 수 있는지(몫)와 그보다 1을 더 낮출 수 있는 개수(나머지)를 계산
4. 주어진 값들을 바탕으로 야근 피로도 계산
   1. 오름차순 정렬된 works 배열에 대해 시작부터 기준 최소값 전까지는 단순 제곱 값을 누적
   2. 이후 남은 개수 중 나머지를 제외하고는 기준 최소값 - 몫의 제곱을 누적
   3. 남은 나머지는 기준 최소값 - 몫 - 1의 제곱을 누적

 문제에서 요구하는 야근 피로도의 최소값을 리턴하기 위해서는 주어진 works 배열 속 몇몇 요소들을 0으로 만드는 과정이 아닌, 특정 값 이상으로 큰 값들을 낮춰 전체적으로 특정 값들에 수렴하게 만들어야 한다 (제곱의 특성 때문에).

 즉 이런 모양의 works 배열들을,

 이렇게 만드는 것보다는,

 이렇게 만드는 것이 제곱 값의 합인 야근 피로도가 더 적게 나온다.

 이를 적용하는 과정은 우선 주어진 works 배열을 오름차순 정렬한 다음, 우선은 0번째 인덱스와 0번째 인덱스의 works 값을 기준선으로 잡고 이후 반복문을 통해 works[i]값과 기준값의 차이를 누적 계산한다. 그리고 만약 해당 누적값(diffWorkSum)이 처리가능한 작업량(n)보다 작다면, 이를 커버가능할 때까지 기준 인덱스(minIndex)와 기준 works 값(minWork)을 올리고 이 때의 diffWorkSum을 구한다.

 그 다음 n값으로 처리가능한 diffWorkSum이 나온다면, 이는 해당 기준 인덱스 이후 works 값들은 모두 최소 기준값으로 만들 수 있다는 말이다. 물론 그렇게 처리하고도 남은 작업량 (n - diffWorkSum)을 더 활용하기 위해 이를 적용가능한 개수 (works.length - minIndex) 로 나눠 몫과 나머지를 구하는데, 여기서 몫은 전체적으로 얼마를 더 낮출 수 있는 지, 나머지는 거기서 1을 더 뺄 수 있는 개수를 나타낸다.

 이후 최종적으로 야근 피로도를 계산하면 된다. 우선 works 배열 시작부터 최소 기준 값으로 잡은 인덱스 전까지는 단순히 제곱값을 누적 계산한다. 그다음에는 적용가능한 개수에서 나머지를 뺀 값은 (minWork - 몫)의 제곱을, 나머지 개수만큼은 (minWork - 몫 - 1)의 제곱을 계산해서 누적하면 답이 나온다.

 

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0, totalWork = 0, diffWorkSum = 0;
        int minWork, minIndex;

        Arrays.sort(works); //정렬
        minIndex = 0;
        minWork = works[0];

        for (int i = 0; i < works.length; i++) {//총 작업량과 기준 과의 차이 누적값을 계산
            totalWork += works[i];
            diffWorkSum += works[i] - minWork;
        }

        if (n >= totalWork) {//총 작업량이 커버가능하다면
            return 0;
        }

        while (n < diffWorkSum) {//현재 누적값이 n으로 커버 불가능하다면 minIndex와 minWork를 높여 계산
            ++minIndex;
            diffWorkSum = diffWorkSum - (works.length - minIndex) * (works[minIndex] - works[minIndex - 1]);
        }

        minWork = works[minIndex];

        //목과 나머지 계산
        long quotient = (n - diffWorkSum) / (works.length - minIndex);
        long remain = (n - diffWorkSum) - quotient * (works.length - minIndex);

        for (int i = 0; i < minIndex; i++) {//과정 1
            answer += works[i] * works[i];
        }

        answer += (minWork - quotient) * (minWork - quotient) * (works.length - minIndex - remain);//과정2
        answer += (minWork - quotient - 1) * (minWork - quotient - 1) * remain;//과정 3

        return answer;
    }
}

결과