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

프로그래머스 야근 지수 문제는 퇴근까지 N시간 남은 회사원 Demi의 야근 피로도를 최소화하는 문제다. 난이도는 레벨3이며 우선순위큐를 활용해 해결할 수 있다.

 

프로그래머스 - 야근 지수 문제 정보

알고리즘 분류

- 그리디 알고리즘

난이도

- Level 3

 

문제 요약

(야근 피로도) = sum( (남은 작업량) ^ 2 )

• 1시간에 작업량이 1이며, 퇴근까지 N시간 남았다.
• 가능한 야근 피로도의 최소값은?

 

문제 풀이 과정 1

핵심 아이디어
제곱들의 합을 최소화시키기 위해서는 숫자들간의 편차를 최소화해야 한다. 따라서 매번 제일 큰 수를 줄여나간다.

• 작업량 배열을 내림차순으로 정렬 후 앞에서부터 단계별로 줄이기
  • [4,3,3] → [3,3,3] → [2,2,2]

코드

public static long solution(int n, int[] works) {
    int W = works.length;

    // 작업량 정렬
    Integer[] sortedWorks = Arrays.stream(works).boxed()
            .toArray(Integer[]::new);
    Arrays.sort(sortedWorks, Collections.reverseOrder());

    while (n > 0) {
        int start = sortedWorks[0];

        if (start == 0) {
            break;
        }

        // 현재 상태에서 가장 큰값들을 1씩 줄임
        // ex) [5,5,3,2,1] -> [4,4,3,2,1]
        for (int idx = 0; idx < W; idx++) {
            if (n > 0 && sortedWorks[idx] == start) {
                sortedWorks[idx]--;
                n--;
            } else {
                break;
            }
        }
    }

    // 최종 야근 지수 계산
    long ans = 0;
    for (int i = 0; i < W; i++) {
        ans += (long) sortedWorks[i] * sortedWorks[i];
    }

    return ans;
}

• 시간복잡도: 정렬 O(WlogW) + 1씩 줄이기 O(N) = O(N+WlogW)
• 공간복잡도: 정렬을 위한 새 배열 O(W)

문제 풀이 과정 2

• 모든 작업량 값을 내림차순 PQ에 넣고, 최댓값을 꺼내서 1 줄이고 다시 넣고를 반복

 

코드

public static long solution(int n, int[] works) {
    int W = works.length;

    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
    for (int j : works) {
        pq.add(j);
    }

    while (n > 0 && !pq.isEmpty()) {
        int top = pq.poll();
        if (top == 0) break;
        pq.add(top -1);
        n--;
    }

    long ans = 0;
    while (!pq.isEmpty()) {
        int work = pq.poll();
        ans += (long) work * work;
    }

    return ans;
}

• 시간복잡도: PQ에 넣기 O(WlogW) + 1씩 줄이기 O(NlogN) = O((N+W)logW)
  • 과정1보다 조금 느리지만 통과 가능한 수준이다.
• 공간복잡도: PQ O(W)