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

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

프로그래머스

난이도: LEVEL3

알고리즘 유형: 그리디 

문제 설명 

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

퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 solution 함수를 완성해라

야근 피로도는 남은 작업량들의 각 제곱 합이다.

 

ex)

works       n       result  

[4, 3, 3]      4       12

 

2, 2, 2 → 2^2 + 2^2 + 2^2 = 12

 

보다시피 각 works의 값이 균일하게 작아야 야근 피로도가 최소화 된다.

 

그래서 현재 남은 작업량 중에서 가장 작업량이 많은 값을 (그리디 하게)

n을 하나 줄이면서 작업량 또한 1 줄인다. 

 

이 작업을 n이 0이 될때까지 반복한다. 

또한 만약 현재 남은 작업량중에 최댓값이 0이라면 남은 작업들도 0이기 때문에 

야근 피로도는 0이다. 이때 바로 0을 반환한다. 

 

시간 복잡도 

처음에 당연히 시간 초과에 걸릴줄 알았지만 

잘 생각해보면 그렇게 많은 시간이 걸리지 않는다.

 

work 최대 길이: 20000

n 최대: 1000000

 

우선 순위 큐에 값을 넣는데 걸리는 시간 O(KlogK) → 20000 * log20000 

n을 끝까지 사용 1000000

 

최악의 경우: 1000000 + 20000 * log20000 1초도 걸리지 않는다. 

정답 코드 

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