문제 소개
숫자 배열을 첫 번째이자 유일한 입력값으로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수의 역할은 원본 배열에서 만들 수 있는 모든 홀수 길이의 하위 배열(부분 배열)을 추출하고, 각 하위 배열의 합을 계산한 뒤 그 총합을 반환하는 것입니다.
여기서 말하는 하위 배열(subarray)이란 배열에서 연속된 요소들로 이루어진 부분 수열을 의미합니다. 즉, 요소들을 임의로 조합한 것이 아니라 원래 배열의 순서를 그대로 유지해야 한다는 점에 유의하세요.
입력 예시
const arr = [1, 2, 3, 4, 5];
이 배열에서 만들 수 있는 모든 홀수 길이의 하위 배열은 다음과 같습니다.
[1], [2], [3], [4], [5],
[1, 2, 3], [2, 3, 4], [3, 4, 5],
[1, 2, 3, 4, 5]
각 하위 배열의 합을 모두 더하면 결과는 다음과 같습니다.
const output = 57;
구현 코드
const arr = [1, 2, 3, 4, 5];
// 배열의 모든 요소 합계를 구하는 헬퍼 함수
const sumArray = (arr = []) => arr.reduce((a, b) => a + b);
// 홀수 길이 하위 배열의 총합을 구하는 함수
const oddSum = (arr = []) => {
let len = 1;
let sum = 0;
const { length } = arr;
while(len <= length){
// 시작 인덱스 i부터 길이 len만큼 잘라내어 합산
for(let i = 0; i + len <= length; i++){
sum += sumArray(arr.slice(i, i + len));
};
len += 2; // 길이를 2씩 늘려 홀수만 순회
};
return sum;
};
console.log(oddSum(arr));
출력 결과
57
코드 동작 원리
이 알고리즘은 두 단계의 반복으로 구성됩니다.
- 외부 while 루프: 하위 배열의 길이(len)를 1, 3, 5처럼 홀수 단위로 증가시키며 전체 배열 길이까지 반복합니다.
- 내부 for 루프: 각 길이에 대해 가능한 모든 시작 위치(i)를 순회하며 slice()로 해당 구간을 잘라낸 후 합계에 누적합니다.
배열 [1, 2, 3, 4, 5]의 경우 길이 1인 하위 배열 5개(합 15), 길이 3인 하위 배열 3개(합 27), 길이 5인 하위 배열 1개(합 15)가 생성되므로 최종 결과는 15 + 27 + 15 = 57이 됩니다.
시간 복잡도 개선하기
위 방법은 slice와 reduce 연산이 반복문 안에서 중첩되어 시간 복잡도가 O(n³)입니다. 배열이 커지면 비효율적일 수 있으므로, 수학적 접근을 통해 O(n)까지 최적화할 수 있습니다.
핵심 아이디어는 각 요소가 홀수 길이 하위 배열에 몇 번 등장하는지를 미리 계산하는 것입니다.
- 인덱스 i의 요소를 포함하는 전체 하위 배열의 개수는 (i + 1) × (n − i)개입니다. 왼쪽 경계의 선택지가 i + 1개, 오른쪽 경계의 선택지가 n − i개이기 때문입니다.
- 이 중 홀수 길이인 경우의 수는 ((i + 1) × (n − i) + 1) / 2, 즉 올림 나누기로 구할 수 있습니다.
const oddSumOptimized = (arr = []) => {
const n = arr.length;
return arr.reduce((sum, num, i) => {
const count = Math.ceil(((i + 1) * (n - i)) / 2);
return sum + num * count;
}, 0);
};
console.log(oddSumOptimized([1, 2, 3, 4, 5])); // 57이 방식은 각 요소를 한 번씩만 방문하므로 대용량 데이터에서도 훨씬 빠르게 동작합니다.