야근 지수

문제 정보

• 프로그래머스 Lv.3
• 문제 링크

풀이

야근 지수는 ‘야근을 시작하는 시점에 남은 일의 작업량을 제곱해서 더한 값’이다.

제곱해서 더하기 때문에, ‘제일 큰 값’을 줄이는 게 중요하다.

매번 정렬하면 시간이 오래 걸리므로, 우선순위 큐를 사용했다. (기본적으로 최소 힙으로 동작하므로)

코드

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