[Java] Lv.3 야근 지수

문제

 

프로그래머스

 

문제 풀이

문제를 보자마자 든 생각이 아 저 works를 내림차순 우선순위 큐에 담아놓으면 되겠구나였다.
n시간 만큼 일을 해서 n만큼의 작업량을 처리하는데 n시간 뒤에 works의 남은 작업량의 제곱수들의 합이 최소값이 되도록 구해야하는 것이다.
 
즉, 각 작업의 남은 작업량이 작을 수록 제곱수들의 합이 작아진다.
만약 7 8 6으로 작업이 남았고 n이 3이다라고 했을 때 
1. 8에서 1시간 작업을 하여 7이 남도록 만든다.
2. 7 둘 중 하나를 작업하여 6이 남도록 만든다.
3. 남은 7 하나를 작업하여 6이 남도록 만든다.
4. 6의 2제곱  + (7의 2제곱 * 2) = 36 + 49+ 49 = 134가 정답이 된다.
 
단순히 큰 값인 8을 3 제거 해서 5를 만들어봐야 의미가 없다.
숫자 n은 크기가 클 수록 제곱했을 때 값이 기하급수적으로 커지기 때문에 가장 큰 수를 -1 하는 것이 가장 중요하다.
7 8 6에서 8을 - 2 해보자 7 6 6이 된다. 이 때 더 높은 숫자인 7이 있는데 6을 -1 해버리는 것은 의미가 없는 것이다.

무슨 소리인지 이해가 안된다면 

7 6 6에서 7을 -1 하는 것과 6을 -1 하는 것을 비교해보자.

6을 뺄 경우 차후 제곱 수를 구할 때 36에서 25로 줄어드는 것이다. (9차이)

하지만, 7을 뺄 경우 차후 제곱 수를 구할 때 49에서 36으로 줄어든다. (13차이)

이제 코드의 설명을 해보자.
각 작업을 내림차순으로 큐에 담고 n만큼 반복하여 가장 큰 값을 꺼내서 -1하여 다시 큐에 집어넣는다.
n번 만큼 작업한 뒤 큐에 있는 모든 값을 꺼내서 제곱하여 더하게 되면 원하는 최소 값이 나올 것이다.

자바 코드

import java.util.*;

class Solution {
    // 내림차 순으로 저장할 큐
    PriorityQueue<Integer> que = new PriorityQueue<>((o1, o2) -> {return o2 - o1;});
    public long solution(int n, int[] works) {
        long answer = 0;
        
        // 각 작업량을 큐에 담기
        for(int work : works)
            que.offer(work);
    
        // n시간만큼 반복
        for(int i = 0; i < n; i++){
            // 높은 작업량을 가진 값을 하나 꺼낸다.
            int temp = que.poll();
            
            // 완료된 작업이면 스킵
            if(temp == 0){
                que.offer(0);
                continue;
            }
            // 작업량을 한 시간 줄이고 다시 큐에 삽입한다.
            que.offer(temp - 1);
        }
        
        // 남은 작업을 다 꺼낸다.
        while(!que.isEmpty()){
            int temp = que.poll();
            // 남은 작업의 제곱수 들을 다 더해준다.
            answer += Math.pow(temp, 2);
        }
        
        return answer;
    }
}