[프로그래머스] 야근지수 (JAVA/자바)

[문제 링크]

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

프로그래머스

 

문제 설명

야근피로도 = (N시간 동안 야근 후 남은 일의 각 작업량^2) 을 모두 더한 값

N시간동안 works 배열에 담긴 각 일의 작업량을 적절하게 처리했을 때, 야근 피로도의 최소값을 구한다.

1시간동안 작업량 1을 처리할 수 있다.

 

 

 

문제 풀이

알고리즘 분류

• 우선순위 큐(PriorityQueue)

야근 피로도의 최소값을 구하려면 작업량이 가장 많은 일부터 처리해서 제곱근의 크기를 작게 한다.

 

PriorityQueue에 현재 남은 작업량을 담고, ollections.reverseOrder()로 내림차순 정렬한다.

n번만큼 반복하면서 작업량이 가장 많은 일부터 -1 한다.

작업량이 0인 경우에는 큐에 다시 넣지 않는다.

 

전체코드

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int w : works) {
            pq.add(w);
        }
        
        while(n > 0 && !pq.isEmpty()) {
            int poll = pq.poll();
            if((poll - 1) > 0) {
                pq.add(poll - 1);
            }
            n--;
        }
        
        while(!pq.isEmpty()) {
            int work = pq.poll();
            answer += work * work;
        }
        return answer;
    }
}