JavaScript로 합이 가장 큰 하위 배열의 인덱스 찾기

문제 이해

숫자들을 담고 있는 배열의 배열(2차원 배열)이 주어졌을 때, 각 하위 배열의 요소 합계를 계산하여 그 합이 가장 큰 하위 배열의 인덱스를 반환하는 함수를 작성해야 합니다. 만약 최대 합을 가진 하위 배열이 여러 개라면, 가장 먼저 등장하는 하위 배열의 인덱스를 반환해야 합니다.

예를 들어 다음과 같은 배열이 있다고 가정해 보겠습니다.

const arr = [[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]];

각 하위 배열의 합은 순서대로 13, 84, 143, 2859입니다. 따라서 네 번째 하위 배열인 [1000, 1001, 857, 1]의 합이 가장 크므로, 결과값은 인덱스 3이 되어야 합니다.

코드 구현

그럼 실제 코드를 작성해 보겠습니다.

const arr = [[4, 5, 1, 3], [13, 27, 18, 26], [32, 35, 37, 39], [1000, 1001, 857, 1]];
const findMaxSubArray = (arr) => {
   const add = (array) => array.reduce((acc, val) => acc + val);
   return arr.reduce((acc, val, ind) => {
      const sum = add(val);
      if(sum > acc.sum){
         return {
            index: ind,
            sum
         }
      };
      return acc;
   }, {
      index: -1,
      sum: -Infinity
   }).index;
};
console.log(findMaxSubArray(arr));

실행 결과

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

코드 동작 원리

이 코드가 어떻게 동작하는지 단계별로 살펴보겠습니다.

add 헬퍼 함수: reduce() 메서드를 활용해 하나의 하위 배열에 포함된 모든 숫자의 합계를 계산합니다.
외부 reduce() 순회: 전체 배열을 순회하면서 누적 객체(acc)에 지금까지 발견한 최대 합과 해당 인덱스를 저장하고, 더 큰 합을 가진 하위 배열을 만나면 값을 갱신합니다.
초기값 설정: 초기값을 { index: -1, sum: -Infinity }로 지정했기 때문에, 모든 요소가 음수인 배열이라도 정확하게 처리할 수 있습니다.
중복 최댓값 처리: 비교 조건을 sum > acc.sum처럼 엄격하게(초과) 설정했으므로, 동일한 최대 합을 가진 하위 배열이 여러 개일 경우 항상 첫 번째 인덱스가 유지됩니다.

이 알고리즘의 시간 복잡도는 O(n × m)입니다. 여기서 n은 하위 배열의 개수, m은 각 하위 배열의 평균 길이를 의미하며, 배열을 한 번만 순회하므로 매우 효율적입니다.