먼저, Demi가 가진 작업량들(works 배열)과 주어진 시간 n이 있습니다. Demi는 1시간에 작업 1만큼을 처리할 수 있으므로, n시간 동안 최대 n만큼의 작업을 줄일 수 있습니다. 문제의 목표는 모든 작업의 남은 작업량을 제곱한 값의 합, 즉 야근 피로도가 최소가 되도록 작업을 처리하는 것입니다.
이 문제를 풀기 위한 핵심 아이디어는, 제곱 함수가 입력값이 커질수록 매우 크게 증가한다는 점에 주목하는 것입니다. 예를 들어, 4의 제곱은 16이고 3의 제곱은 9입니다. 만약 4에서 1을 줄여 3으로 만들면 피로도는 16에서 9로 7만큼 감소하는 반면, 이미 3인 작업에서 1을 줄여 2로 만들면 피로도는 9에서 4로 5만큼 감소합니다. 따라서, 남은 작업량이 가장 큰 작업에 우선적으로 1씩 작업하는 것이 전체 피로도를 줄이는 데 효과적입니다.
이런 이유로, 매 시간마다 남은 작업량이 가장 큰 작업을 선택하여 1만큼 줄이는 그리디(greedy) 전략을 사용합니다. 이를 위해 일반적으로 최대 힙(또는 우선순위 큐를 내림차순으로 구성)을 사용하여, 현재 가장 큰 작업량을 쉽게 찾고, 해당 작업을 1만큼 감소시킨 후 다시 힙에 넣는 과정을 n시간 동안 반복합니다.
또한, 만약 전체 작업량의 합이 n보다 작거나 같다면, 모든 작업을 끝낼 수 있으므로 야근 피로도는 0이 됩니다.
즉, 풀이 과정은 다음과 같습니다:
- 예외 처리: 먼저 모든 작업의 총합이 n 이하인지 확인합니다. 만약 그렇다면, 남은 작업량이 0이 되어 피로도도 0이 됩니다.
- 우선순위 큐(최대 힙) 초기화: 각 작업의 남은 작업량을 최대 힙에 넣습니다. 이 때, 최대 힙을 사용하면 언제나 가장 큰 작업량을 빠르게 찾을 수 있습니다.
- n시간 동안 작업 처리: n번 반복하면서, 힙에서 가장 큰 작업량을 꺼내 1만큼 감소시킵니다. 감소시킨 값이 음수가 되지 않도록 주의하며, 다시 힙에 넣습니다. 이 과정을 n번 수행합니다.
- 야근 피로도 계산: n시간 동안 작업한 후, 힙에 남아있는 모든 작업량에 대해 각각 제곱한 값을 모두 더하여 최종 야근 피로도를 구합니다.
import java.util.Collections;
import java.util.PriorityQueue;
public class OvertimeIndex {
public long solution(int n, int[] works) {
long totalWork = 0;
for (int work : works) {
totalWork += work;
}
if (totalWork <= n) return 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int work : works) {
pq.offer(work);
}
while (n-- > 0) {
int largets = pq.poll();
pq.offer(largets - 1);
}
long answer = 0;
while (!pq.isEmpty()) {
int remain = pq.poll();
answer += (long) remain * remain;
}
return answer;
}
}