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

📌 Problem

배열에는 작업별 양이 정수 형태로 주어진다. 작업들을 퇴근 시간 전에 끝내지 못하면 야근을 해야한다. 야근으로 인한 피로도는 야근이 시작한 시점에서 각 작업별 작업량 제곱의 합이다. 1시간마다 1의 작업을 수행할 수 있고 퇴근 시간까지 N시간이 남았을 때 야근으로 인한 최소 피로도를 반환한다.

예를 들어서 [4, 3, 3]의 작업 목록이 있고 퇴근까지 2시간이 남았으면 [2, 3, 3]으로 작업하면 야근 피로도가 22으로 최소가 된다.

📌 Solution

매 시간마다 어떤 작업을 처리할지를 결정해야 한다. 생각해보면 가장 많이 남은 작업을 처리하는 것이 수학적으로 맞다. 작업량 K와 K-1이 있을 때를 생각해보자.

K 작업량에서 1을 빼면 최종적으로 감소하는 야근 피로도는 $K^2 - (K-1)^2$이 된다. 이를 풀어서 계산하면 2K - 1의 피로도가 줄어든다.

K-1 작업량에서 1을 빼면 최종적으로 감소하는 야근 피로도는 $(K-1)^2 - (K-2)^2$이 된다. 이를 풀어서 계산하면 2K - 3의 피로도가 줄어든다.

결과적으로 더 큰 작업량이 남은 작업을 우선적으로 처리해야하는 것을 알 수 있다.

📌 Code

class Solution {
    public long solution(int n, int[] works) {
        // Works to reverse priority queue
        Queue<Integer> nums = Arrays.stream(works).boxed()
                .collect(Collectors.toCollection((Supplier<Queue<Integer>>) () ->
                        new PriorityQueue<>(Comparator.reverseOrder())));

        // Do job which has the biggest workload left each hour
        while (n-- > 0) {
            Integer num = nums.poll();
            if (num == 0) return 0;
            nums.offer(num - 1);
        }

        // Calculate fatigue
        return nums.stream().mapToLong(num -> (long) Math.pow(num, 2)).sum();
    }
}