JavaScript 이진 탐색으로 하위 배열 분할 시 최대 합계 최소화하기

문제 소개

음이 아닌 정수로 구성된 배열 arr을 첫 번째 인수로, 정수 num(num < arr.length)을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수의 임무는 배열을 비어 있지 않은 연속된 하위 배열 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));

코드 설명

이 솔루션의 핵심은 이진 탐색(Binary Search)을 활용하여 최적의 분할 값을 찾는 것입니다.

탐색 범위의 하한(low)은 배열 내 가장 큰 요소로 설정합니다. 어떻게 분할하더라도 각 하위 배열은 적어도 하나의 요소를 포함해야 하기 때문에, 최대 합은 배열의 최댓값보다 작아질 수 없습니다. 반면 상한(high)은 배열 전체의 합으로 설정합니다. 배열을 하나로 묶으면 전체 합이 곧 최대 합이 되기 때문입니다.

이후 low와 high 사이의 중간값(mid)을 기준으로, 주어진 배열을 mid 이하의 합을 가진 그룹으로 나누면 몇 개의 파트가 만들어지는지 split 함수로 계산합니다. 필요한 파트 수가 num보다 많다면 mid가 너무 작다는 의미이므로 하한을 올리고(low = mid + 1), 그렇지 않다면 상한을 낮추는(high = mid) 방식으로 탐색 범위를 좁혀 나갑니다. 이 과정을 반복하면 최종적으로 남는 low 값이 곧 최대 합이 최소화된 결과가 됩니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.