12927. 야근 지수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12927

제한사항

풀이

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        // 최대 힙을 위한 람다 표현식을 사용한 Comparator 정의
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int work : works) {
            pq.add(work);
        }

        for (int i = 0; i < n; i++) {
            if (pq.isEmpty()) break;
            int maxWork = pq.poll();
            if (maxWork > 0) {
                pq.add(maxWork - 1);
            }
        }

        while (!pq.isEmpty()) {
            int remainingWork = pq.poll();
            answer += (long) remainingWork * remainingWork;
        }

        return answer;
    }
}

회고

야근 지수를 최소화하려면 남은 일 중 작업량이 최대인 것을 먼저 처리해야 한다. 야근 지수는 남은 작업량을 제곱하여 더하기 때문에 큰 작업량을 우선적으로 처리해야 제곱 합이 최소화될 것이다. 1시간에 작업량 1 만큼 처리할 수 있기 때문에, 1시간이 지날 때마다 남은 작업량 중 최대를 매번 찾아야 한다. 작업량 중 최대를 찾기 위해 순회(탐색) 한다면 시간 복잡도가 커질 것이다. 우선순위 큐를 이용한다면 매번 순회할 필요 없이 최대 작업량을 찾을 수 있다. 우선순위 큐는 힙 구조로 구현되었기 때문에, 삽입/삭제는 O(logn), 최대/최소 조회는 O(1) 시간 복잡도를 갖는다.