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

코드 힌트

1. 작업의 균등한 감소:
   • 문제에서 목표는 배열의 각 요소를 제곱하여 그 합을 최소화하는 것입니다. 이를 위해 가장 큰 요소를 중심으로 작업량을 줄여야 합니다.
   • 예를 들어 [4, 3, 3]에서 n = 4일 때, 가능한 한 균등하게 작업량을 줄여 [2, 2, 2]와 같이 만드는 것이 중요합니다. 이렇게 해야 제곱값의 합이 최소화됩니다.
2. 배열 정렬:
   • 작업량을 줄이기 위해서는 배열을 정렬하여 현재 최댓값을 쉽게 찾을 수 있어야 합니다. Arrays.sort()를 사용하면 배열이 오름차순으로 정렬되며, 최댓값이 항상 배열의 마지막에 위치합니다.
   • 하지만 매번 Arrays.sort()를 호출하면 시간 복잡도가 O(n log n)이 되어 효율성 문제가 발생할 수 있습니다. 따라서 전체 배열을 매번 정렬하는 대신, 최댓값이 변경될 때만 필요한 부분을 정렬하는 것이 중요합니다.
3. 효율적인 정렬 알고리즘:
   • 일반적으로 Arrays.sort()는 퀵 정렬을 사용하여 효율적으로 정렬합니다. 퀵 정렬의 평균 시간 복잡도는 O(n log n)이지만, 특정한 배열 상황에서는 다른 정렬 알고리즘이 더 적합할 수 있습니다.
   • 예를 들어, 이미 정렬된 배열에서 하나의 요소만 변경되는 경우, 전체를 다시 정렬하는 대신 삽입 정렬을 사용하여 변경된 요소만 재정렬하는 것이 효율적입니다.
   • 삽입 정렬의 최선의 경우 시간 복잡도는 O(n)입니다. 이 문제에서는 배열이 거의 정렬된 상태로 유지되기 때문에, 삽입 정렬이 매우 효율적으로 작동합니다.
   • 예를 들어 [3, 3, 4]에서 4를 줄여 [3, 3, 3]으로 만들 때, 전체를 다시 정렬할 필요 없이 해당 위치에서만 간단히 삽입 정렬을 수행하면 됩니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public long solution(int n, int[] works) {
        long result = 0;
        int m = works.length - 1;

        // 작업 배열을 정렬하여 가장 큰 작업부터 줄이기
        Arrays.sort(works);

        // n이 0이 될 때까지 작업량 감소
        while (n > 0) {
            insertionSort(works, m);  // 배열을 다시 정렬하여 가장 큰 작업량 찾기
            works[m]--;  // 가장 큰 작업량을 감소
            n--;  // n 감소
        }

        // 남은 작업량 제곱의 합을 계산
        for (int i = 0; i < works.length; i++) {
            if (works[i] > 0) {
                result += works[i] * works[i];
            }
        }

        return result;  // 피로도 총합 반환
    }

    // 삽입 정렬을 사용하여 작업 배열을 정렬
    public static void insertionSort(int[] works, int m) {
        if (m == 0) {
            return;
        }

        // 배열을 내림차순으로 정렬하여 가장 큰 작업량을 끝으로 이동
        for (int i = m; i >= 0; i--) {
            boolean isSorted = false;
            int target = works[i];
            int j = i - 1;
            while (j >= 0 && target < works[j]) {
                works[j + 1] = works[j];
                j--;
                isSorted = true;
            }
            works[j + 1] = target;
            if (!isSorted) {
                break;
            }
        }
    }
}