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

이지연·2025년 12월 29일

코딩테스트 풀이(구현, 자료구조, 알고리즘)

목록 보기

14/50

프로그래머스 문제 URL

야근 n시간 동안 작업량을 줄여 “야근 피로도(제곱합)”를 최소화하는 문제
작업량 배열 works가 주어질 때, 매 시간마다 작업량 1을 줄일 수 있고(0 미만 불가), 최종 피로도 (sum works[i]^2)가 최소가 되도록 만든다.

문제 접근

입력
n : 남은 야근 시간(총 n번 -1을 할 수 있음)
works[] : 각 작업의 남은 작업량

예를 들어,
```
n = 4
works = [4, 3, 3]
```
매 시간 “어느 작업을 1 줄일지” 선택해서 최종 제곱합을 최소화한다.
출력
야근을 n시간 진행한 후, 남은 작업량들의 제곱합(야근 지수)을 반환한다.

제출

import java.util.*;

public class A02힙정렬문제풀이 {

    // 야근지수
    // 그리디(탐욕법) : 지금 당장봤을 때 맞겠는데?싶으면 그리디다 (이게 뭔 소리임)
    public static long solution12927(int n, int[] works) {
        // n: 앞으로 야근할 수 있는 총 시간(= 총 n번의 “-1 작업”을 할 수 있음).
        // works[i]: i번째 작업의 남은 작업량(정수).
        // 1시간에 할 수 있는 일: works 중 하나를 골라서 1만큼 감소시키는 것(0 밑으로는 내려가면 안 됨).
        // 이 때 works 중 가장 큰 값을 빼서 -1 하고 넣어주고, 또 가장 큰 값을 빼서 -1해서 넣어주고... 할 수 있는 시간만큼 다 균등하게 빼줌
        long answer = 0;

        Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 최대힙
        int totalWork = 0;
        for (int i = 0; i < works.length; i++) {
            pq.add(works[i]);
            totalWork += works[i];
        }

        if (totalWork < n) {
            return 0;
        }

        for (int i = 0; i < n; i++) {
            int change = pq.peek() - 1;
            pq.poll();
            pq.add(change);
        }

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

        return answer;
    }
}

핵심 개념

그리디(탐욕) 선택: “매번 가장 큰 작업부터 1 줄이기”

피로도는 제곱합이라서, 큰 값을 그대로 두면 페널티가 급격히 커진다.
그래서 매 시간 “현재 가장 큰 작업량”을 1 줄이는 선택이 직관적으로 가장 유리하다.
이 로직을 코드에서는 “최대힙에서 peek/poll로 최댓값을 꺼내 1 감소 후 다시 삽입”으로 구현한다.

왜 PriorityQueue(최대힙)인가?

매 시간마다 “가장 큰 작업”을 찾아야 한다.
매번 배열을 정렬하거나 선형 탐색으로 최댓값을 찾으면 반복 비용이 커질 수 있다.
최대힙을 쓰면 “최댓값 접근/갱신”이 일관된 패턴으로 구현된다(꺼내서 줄이고 다시 넣기).

0으로 만들 수 있으면 바로 0 반환

if (totalWork < n) return 0;

남은 전체 작업량 합이 n보다 작으면(= n시간 동안 전부 0으로 만들 수 있으면) 최종 제곱합은 0이다.

시간복잡도(큰 그림)

초기 힙 구성: works.length번 삽입
이후 n번 반복: (최댓값 꺼내기 → 1 감소 → 다시 넣기)
마지막 합산: 힙에서 모두 꺼내며 제곱합 계산

즉 “힙 연산을 n번 반복”하는 형태라, n이 크면 반복 비용이 핵심이 된다(그래서 PQ 사용 이유가 명확해진다).

출력 예시(간단 흐름)

입력

n = 4
works = [4, 3, 3]

아이디어:

매 시간 “가장 큰 값”을 1씩 깎아 제곱합을 줄이는 방향으로 진행한다.
최종적으로 남은 배열의 제곱합을 계산해 반환한다.

흔한 실수와 해결

❌ 실수	✅ 해결
총 작업량이 n보다 작은데도 계속 처리	`totalWork < n`이면 바로 0 리턴
최소힙을 써서 매번 최소를 줄임	피로도를 줄이려면 보통 “최대부터 감소” 방향이 필요
매번 정렬해서 최대를 찾음	최대힙(PQ)으로 “최대 꺼내기/갱신” 패턴 고정
감소 후 0 미만 가능성 고려 안 함	문제 조건상 0 미만 불가(총합 체크로 방지)