410. Split Array Largest Sum
문제링크: https://leetcode.com/problems/split-array-largest-sum/
nums를 k개의 연속된 배열로 나눴을 때 그 중 합이 가장 큰 배열이 최소로 되는 결과를 구하는 문제다.
Solution
DFS recursion
먼저 완전 탐색을 통해 문제를 해결해 보았다. 배열을 나누는 모든 방법을 깊이 우선 탐색을 통해 모두 고려해 그 중 가장 작은 결과를 찾아내는 방법이다. 배열에서 앞에 일정한 배열을 덜어내면 나머지는 또다른 같은 문제로 바뀌기 때문에 이를 재귀로 구현해보았다.
Algorithm
getMinSum은 사용할 배열, 이전 최대값, 남은 배열나누는 값을 파라미터로 가진다.- 먼저
count가 1일 경우는 현재 배열이 마지막 배열이 되어 결과(배열들의 최대합)를 반환한다. - 마지막 배열이 아닐 경우 반복문을 통해 앞에서부터 일정한 부분을 잘라 그 배열의 총합을 구한다. 이후 나머지 배열들은
getMinSum의 재귀함수를 통해 결과를 구한다. - 반복문을 통해 가장 작은 배열의 최대합을 구하고 반환한다.
var splitArray = function(nums, k) {
// 주어진 배열을 k개로 나누고 가장 큰 합이 최소로 하는 결과를 구하라
// 1. 나누는 방법 : 연결되서 나눈다.
// 백트래킹: 나누는 방법을 모두 구하고 최솟값을 구한다.
const getMinSum = (arr, max, count) => {
if (count === 1) return Math.max(max, arr.reduce((a, c) => a + c, 0));
let curSum = Infinity;
const maxIdx = arr.length - count + 1;
let sum = 0;
for (let i = 1; i <= maxIdx; i++) {
sum += arr[i - 1];
if (i + 1 <= maxIdx && sum + arr[i] <= max) continue; // pruning
curSum = Math.min(curSum, getMinSum(arr.slice(i), Math.max(max, arr.slice(0, i).reduce((a, c) => a + c, 0)), count - 1));
}
return Math.max(max, curSum);
}
return getMinSum(nums, 0, k);
};
시간초과가 발생했다. 한번 재귀를 실행하는데 n가지의 종류로 배열을 나누고 이를 k번 나누게 된다. 그리고 깊이에 따라 이를 n번 시행하기 때문에 총O(n^2 * k)의 시간복잡도를 가진다. 문제의 요건을 맞추기 위해 시간이 다소 소요된 것으로 보이고 더 좋은 방법을 찾아보기로 했다.
Binary search
문제를 보는 시각을 바꿔 어떻게하면 배열을 잘 나눌 수 있을까가 아닌 목표 최대값을 만족하는 배열이 가능한지로 볼 수 있다. 왜냐하면 가능한지를 알아내는 방법은 Greedy하게 n의 시간복잡도를 통해 알아낼 수 있기 때문이다. 따라서 총합이 가능한지를 판단하면서 가능한 최소값을 찾는 문제로 볼 수 있다. 이 최소값을 찾는 방법은 이진탐색을 통해 구할 수 있다(만족하는 지점을 넘으면 가능하고 아니면 불가능하기 때문).
Algorithm
- 먼저
isPossible은 목표하는 최대값을 만족하는지 Greedy하게 판단하는 함수다. 목표값 보다 작은 경우 최대한 배열을 합치고 크면 나눠 k개 이하의 배열로 나눌 수 있으면 가능한 최대값이 된다. - 이진탐색을 위해 결과가 가능한 범위를 구한다. 최소값은
nums의 가장 큰 수, 최대값은nums의 총합이다. - 최소값과 최대값의 중간값이
isPossible(중간값)을 만족하는지 확인한다. 가능하면 최소값 ~ 중간값 - 1, 불가능하면 중간값 + 1 ~ 최대값을 반복해 탐색한다. - 이진탐색을 통해 가능한 최소값을 구하고 반환한다.
var splitArray = function(nums, k) {
// Binary search
// 목표값(Sum의 최대값)을 정해두고 그것이 가능한지(k개로 분할 가능한지) 찾는 것은 Greedy하게 쉽게 알아낼 수 있다.
// 이 결과값이 가능해지는 순간을 찾기 위해서 Binary Search를 통해 그 지점을 찾는다.
// target은 기본적으로 nums의 가장 큰값 이상이여야 한다.
const isPossible = (target) => {
let count = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum + nums[i + 1] <= target) continue;
else {
if (++count > k) return false;
sum = 0;
}
}
return true;
}
// 이진 탐색
let left = 0; // biggest num
let right = 0; // total sum
for (let num of nums) {
left = Math.max(left, num);
right += num;
}
let result = right;
while (left <= right) {
const med = Math.floor((left + right) / 2);
if (isPossible(med)) {
result = med;
right = med - 1;
} else {
left = med + 1;
}
}
return result;
};
isPossible함수는 O(n)의 시간복잡도로 가능한지 판단할 수 있다. 따라서 O(logn)의 이진탐색과 함께 이 문제를 해결한다면 총 O(nlogn)의 시간복잡도로 문제를 해결할 수 있다. 문제에 Greedy가 통하는 부분이 있다면 이를 이용해 문제를 보는 관점을 바꿔 생각해 봐야할 것 같다.
