[lv3] 야근 지수

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

 

피로도를 최소화 하려면, 남은 작업량을 최대한 평탄화 하면 된다.

e.g. [4,3,3] 일 때 가능한 n에 대해 [2,2,2], [2,2,1], [2,1,1] 등이 목표

 

이를 위해, 항상 가장 많이 남은 작업을 낮춰준다. => 그리디

 

매 순간 남은 작업 중 가장 큰 숫자 (작업량)를 판별해야 하므로, 정렬 대신 내림차순 우선순위 큐를 쓴다.

 

 

import java.util.*;

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

        PriorityQueue<Integer> workQueue = new PriorityQueue<>(Comparator.reverseOrder());

        Arrays.stream(works).forEach(workQueue::offer);

        while(n > 0 && !workQueue.isEmpty()) {

            int w = workQueue.poll();

            if(w > 1) {
                workQueue.offer(--w);
            }

            n--;
        }

        while(!workQueue.isEmpty()) {
            int w = workQueue.poll();
            answer += Math.pow(w, 2);
        }

        return answer;
    }
}