[프로그래머스 Lv3][자바] 야근 지수

❓문제설명

야근지수

프로그래머스

 

 

---

🔍문제해석

어떤걸 풀어야 할까?

• 퇴근까지 남은 시간 int와 해야할 일 int 배열이 주어진다.
• 야근을 한 직장인의 야근 피로도를 구해라.
• 야근 피로도는 퇴근한 시점에서 남은 일들의 작업량을 제곱하여 더한 값이다. 

---

🧐문제풀이

• 문제 풀이 구상
  • 1차 보자마자 DFS를 떠올랐다. 남은 시간과 남은 작업량을 계속 넘기면서 재귀함수를 호출하는 식으로 말이다.빠르게 문제를 풀었고, 주어진 예시로 테스트 했을때에는 모두 정답이 리턴되었다.하지만 제출을 했을때 너무 느려서 pass하지 못했다.아마 작업량 배열을 돌면서 작업량을 빼고 그걸 다시 재귀를 도는 과정에서 많은 시간이 소요되었을 것이다.낙담하던 중 발견한 좋은 풀이 => https://school.programmers.co.kr/questions/76964

• 2차 결론은 남은 작업량들의 편차를 줄이는 것이다. 제곱계산으로 인해 큰 수가 있다면 피로도는 배로 늘어난다.

 

• 알고리즘 선택

다른 작업량보다 월등히 큰 수를 없애기 위해 무리 중 가장 큰 수를 뽑아올 수 있는 우선순위 큐를 사용하였다.

 

---

！제출코드

1. 내림 차순으로 우선순위 큐를 만든다. 가장 큰 원소를 뽑아오기 위함이다.
2. 작업량을 queue에 담는다.
3. 퇴근 시간이 될때까지 가장 큰 작업을 가져와서 빼준다.
4. 계산이 끝나고 남은 작업량들의 제곱을 더해준다.

import java.util.*;
class Solution {
      public static long solution(int n, int[] works) {
      
       	long answer = 0;
        // (1)
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        
        // (2)
        for (int work : works) {
            queue.offer(work);
        }
        
        // (3)
        while (n > 0){
           int current =  queue.poll();
            queue.offer(current > 0?current-1:current );
            n--;
        }
       
       // (4)
        for(int q : queue){
            if(q > 0) answer += (long) Math.pow(q, 2);
        }
        
        return answer;
    }
}