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

프로그래머스 야근 지수
https://programmers.co.kr/learn/courses/30/lessons/12927

야근 피로도를 최소화하기 위해서는 어떻게 해야할까?

남은 일의 작업량이 [4, 3, 3], n = 4일 때 [2, 2, 2]로 만드는 것이 [0, 3, 3]으로 만드는 것 보다 낫다.
직관적으로 남은 일의 양이 균일할 때 피로도가 최소화된다는 감이 올 것이다.

이를 산술적으로 풀이하면 다음과 같다.
단순하게 일이 딱 두 개만 주어졌고, n시간 일하고 남을 일의 총량을 a라고 해보자.
첫번째 일이 x시간 남았다면 두번째 일은 a-x시간 남게 될 것이다.

이 때의 야근 피로도는 다음과 같다.

이 수식은 익숙한 2차 그래프로 표현할 수 있고, x가 a/2일 때, 즉 x와 a-x가 동일해질 때 최소값을 가진다.

따라서 n시간 일한 뒤 남은 일들이 되도록 균일해야 한다.

.
.

나의 경우 이 원칙에 집중해 단순 구현문제로 접근했다.

물론 works를 소팅하여 최대값을 구하고, 가장 많이 남은 업무량이 얼마인지 체크할 수 있도록 maxWork라는 변수를 도입하였으므로, 아래에서 소개할 PriorityQueue와 기저 원리는 동일할 것이다.

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        Arrays.sort(works);
        
        int maxWork = works[works.length-1];
        int len = maxWork+1;
        int[] leftWork = new int[len];
        
        for(int tmp : works) leftWork[tmp]++;
        
        while(maxWork > 0 && n > 0){
            if(leftWork[maxWork] == 0) maxWork--;
            else if(leftWork[maxWork] <= n){
                leftWork[maxWork-1] += leftWork[maxWork];
                n -= leftWork[maxWork];
                leftWork[maxWork] = 0;
                maxWork--;
            } else {
                leftWork[maxWork-1] += n;
                leftWork[maxWork] -= n;
                n = 0;
            }
        }
        
        for(int i = 1 ; i < len ; i++)
            answer += Math.pow(i, 2)*leftWork[i];
        
        return answer;
    }
}

.
.

많은 분들이 이 문제를 PriorityQueue로 접근해 푸셨다.

선입선출의 규칙을 제공하는 일반 Queue와 달리, PriorityQueue는 우선순위가 높은 element를 먼저 내보낸다.
이 원리를 알고 있다면, 위처럼 직접 구현할 필요 없이 비교적 단순하게 접근할 수 있다.

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        
        long answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int work : works)
            pq.add(work);
        
        while(n > 0 && !pq.isEmpty()){
            n--;
            int work = pq.poll()-1;
            if(work > 0) pq.add(work);
        }
        
        while(!pq.isEmpty())
            answer += Math.pow(pq.poll(), 2);
        
        return answer;
    }
}