[프로그래머스 Lv.3] 야근 지수(Java) - 우선순위 큐

📌 핵심 요약

• 야근 지수는 제곱 합 — 작업량 x를 1시간 처리하면 지수는 2x - 1만큼 줄어든다. 이 값은 x가 클수록 크다.
• 매 시간 가장 큰 일감을 1 깎는다 — 최대 힙(PriorityQueue + reverseOrder)으로 최댓값을 꺼내 1 줄이고 다시 넣는다.
• 제곱은 (long) x * x — Math.pow는 오차 보장이 1 ulp라 캐스팅 과정에서 1이 사라질 수 있다.

 

목차

1 문제

프로그래머스 #12927

야근 지수

n ≤ 1,000,000 · works.length ≤ 20,000

난이도: Lv.3

퇴근까지 남은 시간이 n시간이고, 각 일감의 작업량이 배열 works에 담겨 있다. 1시간에 아무 일감이나 하나를 골라 작업량을 1 줄일 수 있다. 퇴근 시점에 남아 있는 각 작업량을 제곱해 모두 더한 값이 야근 지수이며, 이 값의 최솟값을 구하는 문제다.

확인해야 할 것

1. 매 시간 어떤 일감을 고르는 것이 이득인지 판단할 기준
2. 모든 작업량이 0이 되었을 때의 처리
3. 제곱 합의 최댓값이 int 범위를 넘는지 여부

2 어떤 일감을 골라야 하는가

1시간을 쓸 때마다 일감 하나를 골라야 한다. 선택의 기준을 세우려면 어떤 일감을 처리했을 때 야근 지수가 가장 많이 줄어드는지를 알아야 한다. 그래서 감소량을 식으로 구했다.

변수 정의

• x : 지금 그 일감에 남아 있는 작업량
• x² : 그 일감이 야근 지수에서 차지하는 몫
• x - 1 : 1시간 처리한 뒤 남는 작업량, 그때의 몫은 (x - 1)²

구하려는 값은 처리 전 몫에서 처리 후 몫을 뺀 값, 즉 x² - (x-1)²이다. 이 식을 한국어로 옮기면 "이 일감 하나에 1시간을 썼을 때 전체 지수에서 깎여 나가는 양"이 된다.

단계별 전개

단계	하는 일	결과
1	(x-1)²을 펼친다	x² - 2x + 1
2	원래 식에 대입한다	x² - (x² - 2x + 1)
3	괄호를 풀어 부호를 뒤집는다	x² - x² + 2x - 1
4	x²끼리 상쇄한다	2x - 1

왜 2가 곱해지고, 왜 1에는 곱해지지 않는가

x²을 한 변이 x인 정사각형으로 놓고 보면 각 항의 출처가 드러난다. 한 변을 1 줄일 때 떨어져 나가는 칸은 두 종류다.

떨어져 나가는 부분	칸 수	대응하는 항
가로 한 줄	x	+2x
세로 한 줄	x
두 줄이 겹치는 모서리	1 (중복 계산)	-1

가로와 세로 두 줄이 각각 x칸이므로 x에 2가 곱해진다. 반면 두 줄이 만나는 모서리는 x가 아무리 커져도 항상 딱 1칸이다. 두 번 세어졌으니 한 번 되돌려 주는 것이고, 이 칸 수는 x와 무관하므로 상수 -1로 남는다. 2x는 변의 길이에 비례해 늘어나는 항이고 -1은 그렇지 않은 항이라는 점이 두 항의 차이다.

💡

선택 기준

감소량 2x - 1은 x가 커질수록 커진다. 따라서 매 시간 지금 남아 있는 값 중 가장 큰 일감을 1 깎는 것이 항상 최선이다. 이 판단은 매 시간 독립적으로 성립하므로 그리디하게 적용할 수 있다.

동작 추적

works = [4, 3, 3], n = 4로 매 시간의 상태를 따라갔다.

시간	꺼낸 값 x	감소량 2x-1	배열 상태	지수
시작	—	—	[4, 3, 3]	34
1	4	7	[3, 3, 3]	27
2	3	5	[2, 3, 3]	22
3	3	5	[2, 2, 3]	17
4	3	5	[2, 2, 2]	12

3 구현

"가장 큰 값을 꺼내고, 줄인 뒤 다시 넣는다"는 동작이 n번 반복된다. 매번 정렬하면 n번의 정렬이 필요하지만, 최대 힙을 쓰면 꺼내기와 넣기가 각각 O(log m)으로 끝난다. PriorityQueue는 기본이 최소 힙이므로 Collections.reverseOrder()를 생성자에 넘겨 최대 힙으로 만들었다.

   

Java — Solution.java

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        // 최대 힙: 매 시간 가장 큰 작업량을 꺼내기 위함
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int work : works) {
            pq.offer(work);
        }

        for (int hour = 0; hour < n; hour++) {
            int max = pq.poll();
            // 최댓값이 0이면 나머지도 전부 0이므로 지수도 0
            if (max == 0) {
                return 0;
            }
            pq.offer(max - 1);
        }

        long answer = 0;
        for (int remain : pq) {
            answer += (long) remain * remain;
        }
        return answer;
    }
}

두 가지 판단 근거

조기 반환 조건. 최대 힙에서 꺼낸 값이 0이라는 것은 남은 전부가 0 이하라는 뜻이고, 작업량은 음수가 될 수 없으므로 전부 정확히 0이다. 이때 야근 지수는 0이며 시간이 더 남아 있어도 변하지 않으므로 즉시 반환한다. 별도로 총합을 미리 구해 sum ≤ n을 검사할 필요가 없어진다.

마지막 합산의 순회 순서. for (int remain : pq)는 힙의 내부 배열을 순서대로 훑기 때문에 값이 정렬되어 나오지 않는다. 다만 여기서는 전부 더하기만 하므로 순서가 결과에 영향을 주지 않는다. 정렬된 순서가 필요한 상황이었다면 이 순회는 쓸 수 없다.

4 실수했던 부분

남은 총량을 균등 분배하려 했다

처음에는 전체 작업량 합에서 n을 빼고, 그 나머지를 일감 개수로 나눠 고르게 분배하려 했다. 제곱 합은 값이 고를수록 작아지기 때문에 방향 자체는 맞다고 판단했다.

   

Java — 처음 작성한 접근

sum -= n;
long mod = sum / works.length;
long remainder = sum % works.length;

원인. 이 계산은 작업량을 자유롭게 재배치할 수 있다고 가정한다. 그러나 문제에서 허용하는 연산은 줄이는 것뿐이며 늘릴 수는 없다. works = [1, 1, 10], n = 4로 확인했다.

구분	결과 배열	야근 지수	도달 가능 여부
균등 분배 계산	[3, 3, 2]	22	불가능
10만 4번 깎기	[1, 1, 6]	38	가능 (정답)
10을 3번, 1을 1번	[0, 1, 7]	50	가능
1을 2번, 10을 2번	[0, 0, 8]	64	가능

균등 분배가 내놓은 [3, 3, 2]는 원래 1이던 일감을 3으로 올려야 나오는 상태다. 실제 최솟값 38과 22는 차이가 크다.

해결. 전체를 한 번에 계산하려는 시도를 버리고, 매 시간의 선택 기준을 세우는 쪽으로 방향을 바꿨다. 균등 분배는 모든 일감이 목표 수준보다 위에 있을 때만 성립하는 특수한 경우였다. 작업량 편차가 작으면 우연히 정답과 일치하기 때문에 일부 테스트 케이스만으로는 잘못을 알아채기 어렵다.

제곱에 Math.pow를 썼다

합산 부분을 처음에는 answer += (long) Math.pow(remain, 2);로 작성했다.

원인. Math.pow는 double을 받아 double을 반환하며, 자바 명세는 결과가 정확한 값이 아니라 1 ulp 이내라고만 보장한다. 정수 제곱이라고 예외가 아니다. remain이 최댓값 50,000일 때를 따라갔다.

단계	값
수학적 정답	2,500,000,000
이 구간 double의 ulp	약 4.8 × 10-7
명세가 허용하는 반환 범위	2,499,999,999.9999995 ~ 2,500,000,000.0000005
(long) 캐스팅 결과	2,499,999,999 또는 2,500,000,000

아래쪽으로 오차가 생기면 캐스팅이 소수부를 버리면서 1이 통째로 사라진다. 예외도 나지 않고 조용히 틀린 값이 누적된다.

해결. (long) remain * remain으로 바꿨다. 정수 곱셈에는 오차 개념 자체가 없다. 캐스팅 위치가 중요하다.

표현	계산 순서	결과
(long) remain * remain	long × int → long으로 승격 후 곱셈	안전
(long) (remain * remain)	int × int 먼저 → 오버플로 후 캐스팅	음수

⚠️

캐스팅은 곱셈보다 먼저 적용된다

(long)은 단항 연산자라 곱셈보다 우선순위가 높다. 따라서 (long) remain * remain에서 캐스팅은 앞의 remain 하나에만 붙고, 그 뒤 곱셈에서 나머지 피연산자가 long으로 끌려 올라간다. 반대로 괄호로 곱셈 전체를 감싸면 int끼리 곱해 넘친 뒤에 캐스팅되므로 이미 늦다. 50,000² = 2.5 × 10⁹은 int 최댓값 2,147,483,647을 넘는다.

5 규모 판단

제약은 n ≤ 1,000,000, works.length ≤ 20,000, works[i] ≤ 50,000이다.

항목	계산	값
힙 높이	log2(20,000)	약 14.3
루프 1회 비용	poll + offer	약 29회 비교
전체 연산량	106 × 29	약 3 × 107
제곱 합 최댓값	20,000 × 50,0002	5 × 1013

연산량은 자바에서 통과 가능한 범위다. 제곱 합 최댓값이 int를 한참 넘으므로 반환형은 long이어야 한다.

ℹ️

오토박싱 비용

PriorityQueue<Integer>를 쓰므로 offer할 때마다 박싱이 일어난다. Integer 캐시는 -128~127 범위만 재사용하므로 그보다 큰 값은 매번 새 객체가 만들어진다. 최대 10⁶개의 객체가 생성되고 버려지지만 수명이 짧아 신세대 GC 선에서 정리되므로 통과에 지장은 없다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.