JavaScript로 홀수 길이 하위 배열의 전체 합 구하기

문제 개요

정수 배열을 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 먼저 원본 배열에서 만들 수 있는 홀수 길이의 모든 하위 배열(연속 부분 배열)을 생성한 뒤, 해당 하위 배열들의 모든 요소를 합산하여 그 총합을 반환해야 합니다.

예를 들어 입력 배열이 다음과 같다면,

const arr = [1, 2, 3];

출력은 다음과 같아야 합니다.

const output = 12;

그 이유는 원하는 하위 배열이 [1], [2], [3], [1, 2, 3]이며, 이들의 합이 1 + 2 + 3 + (1 + 2 + 3) = 12이기 때문입니다.

해결 방법

가장 직관적인 접근 방식은 두 개의 중첩 반복문을 활용하는 것입니다. 바깥쪽 반복문은 하위 배열의 시작 인덱스(i)를 정하고, 안쪽 반복문은 끝 인덱스(j)를 하나씩 늘려가며 누적합을 유지합니다. 이때 현재 하위 배열의 길이(j - i + 1)가 홀수일 때만 누적합을 최종 결과에 더하면 됩니다.

예제 코드

const arr1 = [1, 2, 3];
const arr2 = [1, 2, 3, 4, 5, 6];

const sumOfOddLengthSubarrays = (arr = []) => {
   let res = 0;
   for(let i = 0; i < arr.length; i++){
      let sum = 0;
      for(let j = i; j < arr.length; j++){
         sum += arr[j];
         // 길이가 짝수인 경우 건너뜀
         if (((j - i + 1) & 1) === 0) {
            continue;
         };
         res += sum;
      }
   };
   return res;
};

console.log(sumOfOddLengthSubarrays(arr1));
console.log(sumOfOddLengthSubarrays(arr2));

코드 설명

• 바깥쪽 반복문의 변수 i는 각 하위 배열의 시작 위치를 나타냅니다.
• 안쪽 반복문의 변수 j는 시작 위치부터 배열 끝까지 범위를 확장하면서 sum에 요소를 계속 더해 누적합을 관리합니다.
• (j - i + 1)은 현재 하위 배열의 길이이며, 비트 연산 & 1을 사용해 홀수 여부를 빠르게 판별합니다. 길이가 짝수면 continue로 건너뛰고, 홀수일 때만 결과값에 더합니다.
• 매번 새로운 배열을 만들지 않고 누적합을 재활용하므로 추가 메모리 없이 O(n²) 시간 복잡도로 효율적으로 해결할 수 있습니다.

출력 결과

코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

12
98

배열 [1, 2, 3]의 경우 홀수 길이 하위 배열인 [1], [2], [3], [1, 2, 3]의 합은 12이며, 배열 [1, 2, 3, 4, 5, 6]의 경우 길이 1, 3, 5인 모든 하위 배열의 요소 합이 98로 계산됩니다.