문제 소개
숫자로 이루어진 배열 arr를 첫 번째 인수로, 정수 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이때 num은 항상 배열의 길이보다 작거나 같다는 조건이 주어집니다. 우리가 만들 함수는 배열에서 연속된 num개의 요소를 골랐을 때 그 합이 가장 커지는 경우를 찾아 해당 합을 반환해야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
const arr = [2, 5, 3, 4, 6]; const num = 2;
이때 기대하는 출력은 다음과 같습니다.
const output = 10;
그 이유는 배열에서 연속된 두 요소의 조합 중 4와 6의 합인 10이 가장 크기 때문입니다.
접근 방법: 슬라이딩 윈도우(Sliding Window)
모든 구간의 합을 매번 처음부터 다시 계산하는 비효율적인 방식 대신 슬라이딩 윈도우 기법을 활용하면 선형 시간(O(n))과 상수 공간(O(1))만으로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 먼저 첫 번째 윈도우(처음 num개 요소)의 합을 계산합니다.
- 이후 윈도우를 한 칸씩 오른쪽으로 밀면서 새로 들어오는 요소는 더하고 빠져나가는 요소는 뺍니다.
- 매 단계마다 현재 합과 지금까지의 최댓값을 비교하여 갱신합니다.
이렇게 하면 각 요소를 딱 한 번씩만 더하고 빼면 되므로 전체 시간 복잡도는 O(n)이 됩니다.
구현 코드
const arr = [2, 5, 3, 4, 6];
const maximumSum = (arr = [], num = 1) => {
// 첫 번째 윈도우(앞의 num개 요소)의 합을 계산
let sum = 0;
for (let i = 0; i < num; i++) {
sum += arr[i];
}
let max = sum;
// 윈도우를 한 칸씩 이동하며 합을 갱신
for (let i = num; i < arr.length; i++) {
sum += arr[i] - arr[i - num]; // 새 요소는 더하고, 윈도우에서 벗어난 요소는 뺌
max = Math.max(max, sum);
}
return max;
};
console.log(maximumSum(arr, 2));
console.log(maximumSum(arr, 3));
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
10 13
동작 원리 살펴보기
num = 3인 경우를 예로 들어 실행 과정을 추적해 보겠습니다.
- 초기 윈도우 [2, 5, 3]의 합은 10입니다.
- 윈도우가 [5, 3, 4]로 이동하면 10 + 4 − 2 = 12가 됩니다.
- 윈도우가 [3, 4, 6]으로 이동하면 12 + 6 − 5 = 13이 됩니다.
따라서 최종 최댓값은 13입니다. num = 2일 때는 [4, 6]의 합인 10이 최댓값이 됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열의 각 요소를 한 번씩만 처리합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 몇 개의 변수만 사용합니다.