문제
음이 아닌 정수 배열 arr을 첫 번째 인수로, 정수 num(num
우리 함수의 임무는 배열을 비어 있지 않은 num개의 연속 하위 배열로 분할하는 것입니다. 배열은 이러한 num 하위 배열 중에서 가장 큰 합계를 최소화하는 방식으로 분할되어야 합니다. 그러면 우리 함수는 하위 배열 사이에 누적된 가장 큰 합계를 반환해야 합니다.
예를 들어, 함수에 대한 입력이 -
인 경우const arr = [5, 1, 4, 8, 7]; const num = 2;
그러면 출력은 다음과 같아야 합니다. -
const output = 15;
출력 설명
원래 배열을 하위 배열로 분할하는 네 가지 방법이 있지만 배열을 [5, 1, 4] 및 [8, 7]의 두 그룹으로 분할하면 이 두 그룹의 합이 가장 작고 이 둘 중 큰 그룹은 다음과 같습니다. 8 + 7 =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