프로그래머스 Lv.3) 야근 지수

야근 지수

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

풀이

N : 야근을 해야하는 총 시간 ~> 1시간 마다 한 작업에 대해 -1을 해줄 수 있음

works[] : 각 작업마다 해야하는 총 일의 양

야근 피로도 = 각 work를 시작하는 시점 + (work의 남은 작업량)^2

이 문제는 위의 세 가지로 정리할 수 있다.

즉 각 작업마다 작업량이 많을 수록 야근 피로도가 쌓이기 때문에, 제곱이 되어 커지는 수를 최대한 줄여주어야하는 문제이다.

그렇다면 여기서 생각해야하는 것은, 최대한 고르게 작업량이 큰 작업들을 줄여주어야 하는 것이다.

그래서 잔여 작업량에 따라 쉽게 작업을 가져와서 남은 작업량을 1 줄여주고, 다시 넣어주어 정렬을 해야한다고 생각했다.

이를 편하게 이용하기위해 PriorityQueue(우선순위 큐)를 사용해 주었다.

 

우선순위 큐에는 작업량이 많이 남은 순서대로 내림차순 저장이 되게, Collections의 reverseOrder 메소드를 이용해 초기화를 해주었다.

n이 0이 될 때까지, 반복문을 돌면서, 우선순위 큐의 맨 앞에 저장된 작업을 불러와, 작업량-1을 해주고, 다시 큐에 넣어주었다.

이 작업을 반복한 후에 Queue에 남은 작업량에 대해 제곱한 수를 더해가며, 야근 피로도를 구했다.

이 때, 한가지 추가해준 점은 우선순위 큐에 남은 작업량이 0인 경우, 로직을 종료한 것이다.

왜냐하면, 작업량이 남지 않았는데 -1을 해주게되면 해당 작업은 -1, -2 수 도 없이 음으로 값이 줄어들 것이고, 이를 제곱해주면 양의 값이 나오기 때문이다. 물론, 음의 값은 제곱을 하지 않는 조건문을 걸어주면 피할 수 있겠지만, 큐에 최대 잔여 작업이 0이라면 남은 작업들도 0일텐데 굳이 작업량을 줄여줄 필요가 없다고 생각한다.

 

로직

 

1. 내림차순으로 정렬할 수 있는 우선순위 큐를 만든다.

2. 입력받은 모든 작업을 우선순위 큐에 저장한다.

3. N이 0이 될 때 까지, 모든 시간을 소모하여 우선순위 큐의 맨 앞에있는 작업량에 -1을 해준 뒤, 다시 우선순위 큐에 넣어준다.

 3-1. 우선순위 큐의 맨 앞의 작업이 잔여 작업량이 0이라면 반복문을 종료해준다.

4. 우선순위 큐에 남아있는 모든 값에 대해 제곱한 값을 정답에 더해준다.

 

기억에 남길 것 : Collections.reversOrder() 메소드

 

코드

import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
    public long solution(int n, int[] works) {
        PriorityQueue<Integer> workQ = new PriorityQueue<>(Collections.reverseOrder());
        long answer = 0;
        
        for(int work : works) {
            workQ.offer(work);
        }
        
        while(n !=0) {
            int tmp = workQ.poll();
            if(tmp ==0) {
                break;
            }
            workQ.offer(--tmp);
            n--;
        }
        for(int num : workQ) {
            answer += Math.pow(num,2);
        }
        
        return answer;
    }
}