프로그래머스 - 야근 지수(Java)

힙 문제입니다.

 

일의 작업량이 정수 배열로 주어지고 야근 까지 남은 시간 n이 주어졌을 때, 야근 지수를 가장 적게 만들도록 하는 문제입니다.

야근 지수는 야근 이후에 남은 일의 작업량 원소들의 제곱 합 입니다.

 

그림에서 알 수 있듯이, a의 값이 클 수록 그 제곱의 크기는 급격히 커지게 됩니다.

따라서 일의 작업량을 처리할 때, 가장 큰 숫자부터 제거하는 방식을 사용해야 합니다.

 

자바의 PriorityQueue는 최소힙 입니다.

즉, 가장 작은 숫자부터 값을 빼낼 수 있는 구조이기 때문에 역순으로 돌려서 사용해야 합니다.

 

[구현 코드]

import java.util.*;

class Solution {
    public static 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){
            if(pq.size()>0) {
                int p = pq.poll();
                if(p-1>0) {
                    pq.add(p - 1);
                }
                n--;
            }else break;
        }

        for (Integer integer : pq) {
            answer += Math.pow(integer, 2);
        }

        return answer;
    }
}