[프로그래머스] 야근 지수

문제

코딩테스트 연습 - 야근 지수

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• 각 일에 대한 작업량 works가 주어집니다.
• N시간 동안 업무를 수행하여 야근 피로도를 최소로 하려고 합니다.
• 이때 1시간 작업량 1 만큼 처리할 수 있습니다.
• 야근 피로도는 N 시간 작업 후, 각 작업의 남은 작업량을 제곱하여 더한 값입니다.

입력 조건

• works 길이 : 1 ~ 20,000
• works 원소 : 1 ~ 50,000
• N : 1 ~ 106

출력

야근 피로도 최소화한 값을 반환.

---

문제 풀이

A라는 작업에 남은 작업량을 a라고 했을 때, 1시간을 A에 투자했을 때 감소하는 야근 피로도는 a2 - (a - 1)2 = 2a - 1 입니다.

즉, 현재 작업량 a가 클수록 피로도 감소량도 더 커지게 됩니다. 따라서 매 순간 남은 작업량이 가장 큰 작업을 선택하는 것이 최적입니다.

따라서 최대 힙을 사용하여 항상 가장 큰 값을 꺼내고, 1 만큼 감소시킨 뒤 다시 삽입하는 과정을 반복하면 됩니다.

---

풀이 코드

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

class Solution {
    public long solution(int n, int[] works) {
        // 최대 힙 생성.
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for (int w: works) {
            queue.add(w);
        }
        
        for (int i = 0; i < n; i++) {
            if (queue.isEmpty()) {
                break;
            }
            
            int max = queue.poll() - 1;
            
            // 작업이 완료된 경우 다시 큐에 삽입 X
            if (max != 0) {
                queue.add(max);
            }
        }
        
        // 피로도 계산.
        long answer = 0;
        
        for (int d : queue) {
            answer += (long) d * d;
        }
        
        return answer;
    }
}