그리디 + PQ (PRO 야근지수)

https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < works.length; i++) {
            pq.offer(works[i]);
        }
        
        while (n-- > 0) {
            int temp = pq.poll();
            if (temp > 0) temp--;
            pq.offer(temp);
        }
        
        long answer = 0;
        while (!pq.isEmpty()) {
            answer += Math.pow(pq.poll(), 2);
        }
        return answer;
    }
}

 

 

• 그리디 알고리즘: 매번 가장 큰 작업량을 선택해서 1씩 줄이는 방식이 최적의 해를 보장합니다. 그리디 알고리즘은 각 단계에서 가장 좋은 선택을 해서 문제를 해결하는 방법으로, 이 문제에서는 가장 큰 작업량을 줄이는 것이 전체 야근 피로도를 최소화하는 최선의 선택입니다.
• 우선순위 큐 (Priority Queue): 작업량이 큰 것부터 차례대로 줄여야 하기 때문에, 항상 최대값을 효율적으로 추출할 수 있는 자료구조가 필요합니다. 이때 최대 힙으로 동작하는 우선순위 큐가 적합합니다.