문제
음이 아닌 정수 배열 arr을 첫 번째 인수로, 정수 num(num
우리 함수의 임무는 배열을 비어 있지 않은 num개의 연속 하위 배열로 분할하는 것입니다. 배열은 이러한 num 하위 배열 중에서 가장 큰 합계를 최소화하는 방식으로 분할되어야 합니다. 그러면 우리 함수는 하위 배열 사이에 누적된 가장 큰 합계를 반환해야 합니다.
예를 들어, 함수에 대한 입력이 -
그러면 출력은 다음과 같아야 합니다. -
원래 배열을 하위 배열로 분할하는 네 가지 방법이 있지만 배열을 [5, 1, 4] 및 [8, 7]의 두 그룹으로 분할하면 이 두 그룹의 합이 가장 작고 이 둘 중 큰 그룹은 다음과 같습니다. 8 + 7 =15로 함수가 반환해야 합니다.
이에 대한 코드는 -
여기에서 이진 검색을 사용하여 최상의 분할을 찾을 수 있는지 확인했습니다.
콘솔의 출력은 -const arr = [5, 1, 4, 8, 7];
const num = 2;
const output = 15;
출력 설명
예시
const arr = [5, 1, 4, 8, 7];
const num = 2;
const splitArray = (arr = [], num = 1) => {
let max = 0;
let sum = 0;
const split = (arr, mid) => {
let part = 1;
let tempSum = 0;
for (let num of arr) {
if (tempSum + num > mid) {
tempSum = num;
part++;
} else {
tempSum += num;
}
}
return part;
};
for (let num of arr) {
max = Math.max(max, num);
sum += num;
};
let low = max;
let high = sum;
while (low < high) {
let mid = Math.floor((high+low)/2);
let part = split(arr, mid);
if (part > num) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
console.log(splitArray(arr, num)); 코드 설명:
출력
15