- Published on
- •👁️
야근 지수
- Authors
- Name
- River
문제 설명
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
제한사항
works는 길이 1 이상, 20,000 이하인 배열입니다.works의 원소는 50000 이하인 자연수입니다.n은 1,000,000 이하인 자연수입니다.
입출력 예
입력
n = 4, works = [4, 3, 3]
출력
12
설명
n=4 일 때, 남은 일의 작업량이 [4, 3, 3] 이라면 야근 지수를 최소화하기 위해 4시간동안 일을 한 결과는 [2, 2, 2]입니다. 이 때 야근 지수는 2² + 2² + 2² = 12 입니다.
입력
n = 1, works = [2, 1, 2]
출력
6
설명
n=1일 때, 남은 일의 작업량이 [2,1,2]라면 야근 지수를 최소화하기 위해 1시간동안 일을 한 결과는 [1,1,2]입니다. 야근지수는 1² + 1² + 2² = 6입니다.
입력
n = 3, works = [1, 1]
출력
0
설명
남은 작업량이 없으므로 피로도는 0입니다.
풀이 접근법
시간복잡도 : O(N log N)
공간복잡도 : O(N)
사용 알고리즘 :
그리디우선순위 큐
핵심 포인트 :
- 가장 큰 작업량부터 처리하는 것이 최적
- 최대 힙을 사용하여 항상 가장 큰 작업량을 빠르게 찾음
- 모든 작업이 0이 되면 더 이상 처리할 필요 없음
경계값/반례 :
- 모든 작업을 완료할 수 있는 경우
- 작업량의 제곱 합이 int 범위를 초과하는 경우
핵심 아이디어
- 가장 큰 작업량부터 처리하는 것이 야근 피로도 최소화에 최적
- 제곱의 합이므로 큰 수를 줄이는 것이 효과적 (5² + 3² = 34 > 4² + 4² = 32)
- 최대 힙을 사용하여 항상 가장 큰 작업량을 O(log N) 시간에 찾음
- 모든 작업이 0이 되면 더 이상 처리할 필요 없음
해결 방법
- 최대 힙(우선순위 큐)을 사용하여 작업량들을 관리
- N시간 동안 반복하며 가장 큰 작업량을 1씩 감소
- 작업량이 0이 되면 더 이상 처리할 작업이 없으므로 종료
- 남은 작업량들의 제곱의 합을 계산하여 반환
핵심 패턴
1️⃣ 최대 힙을 이용한 그리디 전략
// 최대 힙으로 가장 큰 작업량을 항상 처리
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < n; i++) {
int work = pq.poll();
if (work == 0) break; // 모든 작업 완료
pq.add(work - 1); // 1시간 작업 후 다시 추가
}
- 매 시간마다 가장 큰 작업량을 선택하여 처리
- 제곱의 합 특성상 큰 수를 줄이는 것이 가장 효과적
2️⃣ 작업 완료 조건 체크
if (work == 0) break;
- 최대 힙에서 꺼낸 값이 0이면 모든 작업이 완료된 상태
- 더 이상 처리할 작업이 없으므로 반복문 종료
3️⃣ 자료형 주의
long sum = 0; // 함수 반환 타입에 맞게 long 사용
while (!pq.isEmpty()) {
int num = pq.poll();
sum += num * num;
}
- 함수 반환 타입이 long으로 지정되어 있음
- 내부 계산도 long으로 일치시켜야 함
1차 제출 코드 ❌
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < works.length; i++) {
pq.add(works[i]);
}
for (int i = 0; i < n; i++) {
int work = pq.poll();
if (work == 0) break;
pq.add(work - 1);
}
int sum = 0; // ❌ int 사용
while (!pq.isEmpty()) {
int num = pq.poll();
sum += num * num;
}
return sum;
}
}
실패 원인
- 효율성 테스트 실패 발생
- 정답 코드와 다른 점은
int sum = 0;뿐이다. - 함수 반환 타입이 long인데 내부에서 int로 계산하는 단순한 실수였다.
- works의 원소 최댓값이 50,000이고 배열 길이가 20,000까지 가능하므로, 최악의 경우 제곱의 합이 int 범위(약 21억)를 초과할 수 있다.
- 작은 케이스에서는 통과하지만 큰 값들의 제곱 합에서 오버플로우가 발생한다.
최종 제출 코드
⭕ 방법 1 : 우선순위 큐
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < works.length; i++) {
pq.add(works[i]);
}
for (int i = 0; i < n; i++) {
int work = pq.poll();
if (work == 0) break;
pq.add(work - 1);
}
long sum = 0; // ✅ long 사용
while (!pq.isEmpty()) {
int num = pq.poll();
sum += num * num;
}
return sum;
}
}
⭕ 방법 2 : 이분 탐색
import java.util.*;
class Solution {
public long solution(int n, int[] works) {
int left = 0;
int right = Arrays.stream(works).max().orElse(0);
while (left < right) {
int mid = (left + right) / 2;
int sum = 0;
for (int work : works) {
if (work < mid) {
continue;
}
sum += work - mid;
}
if (n >= sum) {
right = mid;
} else {
left = mid + 1;
}
}
int remaining = n;
for (int i = 0; i < works.length; i++) {
if (works[i] > left) {
remaining -= works[i] - left;
works[i] = left;
}
}
for (int i = 0; i < works.length && remaining > 0; i++) {
if (works[i] == left && left > 0) {
works[i]--;
remaining--;
}
}
long total = 0;
for (int work : works) {
total += (long) work * work;
}
return total;
}
}
- 코드가 훨씬 복잡하다.
- 시간 복잡도 차이
n=n,m=works.length,max = 배열의 요소 최댓값- 우선순위 큐
- O(n log m)
- 이분탐색
- O(m log max)