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

 

• 알고리즘 분류: 우선순위 큐, 구현, 시뮬레이션
• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927

프로그래머스

 

【 문제 】

 

• 야근 피로도는 works 배열 각 요소들의 제곱의 합이다.
• 주어진 n을 통해 works 에서 주어진 각 일들의 작업량을 1씩 줄일 수 있다.
• 이때, 야근 피로도를 최소로 줄였을 때의 그 야근 피로도를 반환하는 문제이다.

 

 

 

【 풀이 】

 

1. 가장 작업량이 많은 일을 먼저 처리하는 것이 이득이다.
2. 따라서 works 배열을 내림차순으로 정렬한다. -> Collections.reverseOrder()를 이용한 우선순위 큐 사용
3. n만큼 반복하면서 가장 큰 값(pq.peek())의 작업량을 1 줄인다.
4. 우선순위 큐가 빌 때까지 작업량의 제곱을 더한 값을 반환한다.

• 시간 복잡도: O(nlogn) - 우선순위 큐(힙)의 전체적인 시간 복잡도가 O(log n)이다.
• 공간 복잡도: O(n)

 

 

 

【 코드 】

 

public class Programmers_12927 {
    public long solution(int n, int[] works) {
        long sum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i : works) {
            pq.add(i);
        }
        while (n-- > 0) {
            int max = pq.poll();
            if (max > 0) {
                pq.add(max - 1);
            } else {
                break;
            }
        }
        while (!pq.isEmpty()) {
            int work = pq.poll();
            sum += (long) work * work;
        }
        return sum;
    }
}