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

문제

programmers.co.kr/learn/courses/30/lessons/12927

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

풀이

works 배열의 원소에서 n만큼 뺀 값중 나머지에 대해 제곱의 합이 최소인 값을 찾는 문제이다.

제곱의 합이 최소가 되기 위해서는 works의 각 숫자들이 전체적으로 균형이 맞아야 한다. 

 

예를 들어 첫 번째 예제 입력의 경우, works = {4, 3, 3}이고 n이 4이다.

이때 n시간을 모두 첫 번째 일을 처리하는데 사용하면 남는 시간은 0, 3, 3이 될 것이고 야근 지수는 18이 된다.

그러나 전체적으로 균형있게 줄여 2, 2, 2로 만들면 야근지수는 12가 되고 이는 최소값이 된다.

 

남은 수를 '제곱'해서 더하기 때문에 큰 수를 최대한 줄이는 것이 관건이다. 이를 해결하기 위해 우선순위 큐를 사용하였다. 일반적인 우선순위큐는 오름차순 정렬이기 때문에 이를 Collections.reverseOrder()를 사용하여 내림차순으로 바꾸어 큰 시간 부터 해결하였다.

 

q에 담긴 값 중에서 제일 큰 값을 꺼내어 일을 한 시간 줄여주고, 남은 시간도 줄여주면서 연산을 하였다. 이후 다시 q에 넣어주어 다시 값들이 정렬하고 다시 큰 값을 꺼내어 줄여주기를 반복하여 전체적으러 균형이 맞을 수 있도록 하였다.

 

코드

import java.util.*;
class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < works.length; i++) {
            q.offer(works[i]);
        }
        
        while(n > 0) {
            int work = q.poll();
            if(work == 0) break; //더 이상 줄일 수 있는 일이 없음.
            work -= 1; //일 한시간 줄인다.
            q.offer(work);
            n -= 1; // 남은 작업 시간 한시간 줄인다.
        }
        
        long answer = 0;
        for(int work : q) {
            answer += work * work;
        }
        return answer;
    }
}