[Java] LeetCode 410: Split Array Largest Sum

[문제 바로 가기] - Split Array Largest Sum

유형 : 매개 변수 탐색

문제 해석

간단히 nums 배열을 k개의 연속된 부분 배열로 나누고, 나누어진 부분 배열들 중 합이 최대인 배열의 최솟값을 구하는 것이다.

이게 무슨 말인지 예제로 설명해보자면 다음과 같다.

nums = [7,2,5,10,8], k = 2

주어진 nums 배열을 k개, 즉 2개의 부분 배열로 나누면 4가지가 된다.

[7], [2, 5, 10, 8]
[7, 2], [5, 10, 8]
[7, 2, 5], [10, 8]
[7, 2, 5, 10], [8]

각 경우에서 합이 최대인 배열은 각각 25, 23, 18, 24가 된다. 이 최댓값들 중 가장 작은 값을 구하면 된다.

---

💡 아이디어

이 문제는 이진 탐색을 활용한 매개 변수 탐색으로 풀이할 수 있다.

따라서 배열의 크기가 1일 경우를 대비하여 start는 nums 배열에서 가장 큰 값, 배열의 크기가 nums의 길이만큼일 경우를 대비하여 end는 nums 배열의 합으로 설정한다.

부분 배열을 더해가며 합이 mid보다 클 경우 그룹의 수인 count를 하나씩 더해준다. 배열 탐색이 끝났을 때 count가 k보다 클 경우 mid를 높여야하므로 start = mid + 1, k보다 작거나 같을 경우 end = mid가 된다.

---

풀이

class Solution {
    public int splitArray(int[] nums, int k) {
        int start = 0;
        int end = 0;

        for (int num : nums) {
            start = Math.max(start, num);
            end += num;
        }

        while (start < end) {
            int mid = start + (end - start) / 2;
            
            int count = 1;
            int sum = 0;

            for (int num : nums) {
                if (sum + num > mid) {
                    count++;
                    sum = num;
                } else {
                    sum += num;
                }
            }

            if (count <= k) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}