문제 소개
숫자로 이루어진 배열을 첫 번째 인수로, 하나의 숫자를 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 배열 안에서 연속된 요소들로 이루어진 부분 배열(subarray) 중 그 합이 두 번째 인수로 전달된 값과 정확히 일치하는 구간의 총 개수를 찾아 반환해야 합니다.
이 문제에서는 배열의 모든 요소가 양수라고 보장됩니다. 이 조건 덕분에 슬라이딩 윈도우(sliding window) 기법을 안전하게 적용할 수 있습니다.
문제 예시
입력이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 1, 1]; const sum = 2;
이때 출력은 2가 되어야 합니다. 배열에서 합이 2가 되는 구간은 인덱스 0~1의 [1, 1]과 인덱스 1~2의 [1, 1], 정확히 두 개이기 때문입니다.
접근 방법: 슬라이딩 윈도우와 투 포인터
모든 요소가 양수라면 다음과 같은 성질이 성립합니다.
- 윈도우의 오른쪽 끝을 확장하면 구간 합이 증가합니다.
- 윈도우의 왼쪽 끝을 축소하면 구간 합이 감소합니다.
이 특성을 활용하면 불필요한 재계산 없이 목표 합을 만족하는 구간을 효율적으로 탐색할 수 있습니다. 각 시작 지점마다 투 포인터로 일치하는 구간이 존재하는지 확인하고, 그 결과를 모두 더하면 원하는 답을 얻을 수 있습니다.
구현 예제
const arr = [1, 2, 3, 4, 5];
const sum = 5;
// 주어진 시작 지점부터 목표 합을 만족하는 구간이 있는지 확인
const findOne = (arr, target, start = 0) => {
let left = start, right = start, windowSum = 0;
while (right < arr.length) {
windowSum += arr[right];
if (windowSum === target) {
return true;
} else if (windowSum < target) {
right++; // 합이 부족하면 윈도우 확장
} else {
windowSum -= arr[left]; // 합이 초과하면 왼쪽 요소 제거
left++;
if (left > right) {
right = left;
windowSum = 0;
}
}
}
return false;
};
// 모든 시작 지점을 순회하며 일치하는 구간의 개수 집계
const findAll = (arr = [], target) => {
let count = 0;
for (let i = 0; i < arr.length; i++) {
count += findOne(arr, target, i);
}
return count;
};
console.log(findAll(arr, sum));
console.log(findAll([1, 1, 1], 2));참고: 윈도우 축소 시 반드시
arr[left]값을 빼야 합니다. 인덱스 값 자체를 빼면 배열 요소에 따라 잘못된 결과가 나올 수 있으므로 주의하세요.
출력 결과
콘솔에는 다음과 같이 출력됩니다.
2 2
시간 복잡도 분석
각 시작 지점에 대해 최대 배열 길이만큼 탐색하므로 전체 시간 복잡도는 O(n²), 공간 복잡도는 O(1)입니다. 배열 크기가 크지 않다면 충분히 실용적인 성능입니다.
마무리 팁
만약 배열에 음수가 포함될 수 있다면 슬라이딩 윈도우 기법을 사용할 수 없습니다. 이 경우 누적 합(prefix sum)과 해시맵을 조합한 O(n) 풀이를 사용하는 것이 일반적입니다. 다만 이 문제처럼 모든 요소가 양수라면 위에서 소개한 투 포인터 방식이 가장 직관적이고 효율적인 선택입니다.