프로그래머스 Java Lv3 야근 지수

 

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

 

해당 문제는 우선순위 큐를 이용하면 간단하게 풀 수 있다.

이 문제는 남은 시간 n과 각 일에 대한 작업량 works 가 주어진다.

야근 피로도는 각 일에 대한 작업량의 제곱의 합 이므로 이를 최소화하기 위해서는 가장 많이 남은 일부터 처리하면 된다.

즉, 내림차순으로 정렬된 우선순위 큐를 이용하면 가장 많이 남은 일을 쉽게 구할 수 있고,
n번 반복을 통해 가장 많이 남은 일을 처리하면 된다.

간단한 예를 통해 확인해보자.
남은 일이 [7, 1, 1] / [5, 2, 2] / [3, 3, 3] 인 3가지 경우를 생각해보자.
3가지 경우 모두 남은 일의 총합은 9이다. 다만 각각의 일에 대해 남은 작업량이 모두 다르다.

[7, 1, 1]의 경우 야근 피로도는 7^2 + 1^2 + 1^2 = 51
[5, 2, 2]의 경우 야근 피로도는 5^2 + 2^2 + 2^2 = 33
[3, 3, 3]의 경우 야근 피로도는 3^2 + 3^2 + 3^2 = 27

남은 일들의 편차가 최소인 경우가 야근 피로도를 최소화하는 것을 알 수 있다.
다시 말해 남은 일들의 편차를 최소화하는 순서 = 가장 많이 남은 일부터 처리하면 되는 것 이다.

 

이를 코드로 표현하면 다음과 같다.

import java.util.PriorityQueue;
import java.util.Collections;

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 );

        for( int i = 0 ; i < n; i++){
            int work = pq.poll();
            if ( work == 0 ) return 0; //가장 많이 남은 일이 0 //남은 일이 없다
            
            pq.add( work - 1 );
        }
    
        while (!pq.isEmpty()) {
            answer += (Math.pow( pq.poll(), 2));
        }
        return answer;
    }
}