주요 포인트 한눈에 보기
연속 부분수열의 합이 특정 값 M이 되는 경우의 수를 구하는 문제는, 입력 크기가 커질수록 시간 복잡도 차이가 그대로 결과로 이어집니다. 본문에서는 비교 목적의 O(n²) 접근을 먼저 점검한 뒤, 자연수 배열에서 투 포인터(슬라이딩 윈도우)가 O(n)으로 동작하는 근거와 구현 포인트를 정리합니다.
문제
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.
입력설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
수열의 원소값은 1,000을 넘지 않는 자연수이다.
출력설명
첫째 줄에 경우의 수를 출력한다.
입력예제 1
8 6
1 2 1 3 1 1 1 2
출력예제 1
3이 문제는 “연속 구간”만 허용한다는 점이 핵심입니다. 즉, 시작 인덱스와 끝 인덱스가 정해지면 그 사이의 합이 곧 정답 판정 대상이 됩니다.
또한 입력 조건에서 배열 원소가 자연수라는 점이 매우 중요합니다. 자연수(양수)이면 구간을 확장할수록 합이 줄지 않는 단조성이 생기고, 이 단조성이 투 포인터(슬라이딩 윈도우)를 가능하게 만듭니다.
실무/코테 관점에서는 “N이 100,000까지 가능하다”는 제약이 곧 알고리즘 선택 기준입니다. O(n²)은 최악 케이스에서 시간 제한을 넘길 가능성이 높습니다.
내가 푼 정답 (O(n²) 시도)
지난 시간에 투 포인터(슬라이딩 윈도우) 방식으로 같이 풀어봐서 알지만, 같은 문제라도 다른 방식으로 접근했을 때 어떤 단점이 생기는지 확인해보기 위해 O(n²)에 가까운 탐색 구조로 먼저 풀어봤습니다. 관련 내용은 투 포인터 알고리즘(1), 투 포인터 알고리즘(2)에서 이어집니다.
이 섹션에서는 “정답을 바로 최적화로 가는 과정”이 아니라, 왜 O(n²) 접근이 위험한지(그리고 어디서 틀릴 수 있는지)를 코드와 함께 구체적으로 확인합니다.
function solution(m, arr) {
let result = arr.reduce((acc, cur, curIdx, array) => {
let count = acc;
let sum = cur;
let nextIdx = curIdx + 1;
while (sum < m + 1 && nextIdx < array.length) {
sum += arr[nextIdx];
nextIdx++;
if (sum === m) {
count++;
}
}
return count;
}, 0);
return result;
}
let a = [1, 2, 1, 3, 1, 1, 1, 2];
console.log(solution(6, a));입력예제
6
1 2 1 3 1 1 1 2
출력예제
3동작 설명: 각 인덱스를 시작점으로 잡고(curIdx), 뒤쪽 원소를 하나씩 더해가며(nextIdx) 합이 m이 되는 순간을 카운트합니다. 한 번의 시작점에서 “연속 구간”을 오른쪽으로만 확장하는 형태입니다.
메커니즘 해설: 바깥 반복이 reduce로 감싸져 있을 뿐 실질적으로는 “시작점 n개” × “확장 최대 n개” 구조입니다. 즉, 최악의 경우 모든 시작점에서 끝까지 더해보게 되어 O(n²)에 수렴합니다.
실수 포인트와 개선 방향: 이 문제는 원소가 자연수(양수)라서, 합이 목표값을 초과한 이후에는 더 확장해도 다시 목표값으로 돌아올 수 없습니다. 따라서 시작점을 고정하고 뒤로 확장하는 방식이라면 sum > m에서 조기 종료하는 형태가 더 명확합니다. 또한 현재 구현은 sum을 cur로 시작하면서도 “시작하자마자 sum === m인지”를 검사하지 않아, 단일 원소가 정답인 케이스([m])를 누락할 수 있습니다. 마지막으로 구조 자체가 시작점마다 누적합을 다시 만들기 때문에, 입력 크기(N 최대 100,000)에서는 최악 O(n²)로 시간 초과 위험이 커집니다.
정답은 왜 정답인지 풀이
정답 풀이의 핵심은 “구간 합을 다시 계산하지 않는다”는 점입니다. 구간을 오른쪽으로 늘리면 합이 커지고, 합이 너무 커지면 왼쪽을 줄여 합을 낮춥니다. 이 과정에서 lt와 rt는 뒤로 가지 않고 한 방향으로만 움직이므로 전체 작업량이 O(n)으로 수렴합니다.
이 방식은 문제 조건(원소가 자연수)에서만 안정적으로 성립합니다. 자연수라서 단조성이 보장되기 때문에, “커졌으면 줄인다”라는 규칙이 논리적으로 맞아떨어집니다.
기본 예제: 경우의 수만 세는 투 포인터
function solution(m, arr) {
let answer = 0;
let lt = 0;
let sum = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum >= m) {
sum -= arr[lt++];
if (sum === m) answer++;
}
}
return answer;
}
console.log(solution(6, [1, 2, 1, 3, 1, 1, 1, 2]));동작 설명: 오른쪽 포인터 rt로 구간을 확장하며 sum을 증가시킵니다. 합이 목표 이상이 되는 순간부터는 왼쪽 포인터 lt를 이동시켜 합을 줄이며, 줄이는 과정에서도 목표값을 만들면 카운트합니다.
메커니즘 해설: 각 원소는 “더해지는 순간”이 한 번, “빼지는 순간”이 한 번뿐입니다. 즉, rt는 0→N-1, lt도 0→N까지 각각 최대 N번 이동합니다. 이 구조가 곧 선형 시간의 근거입니다.
실수 포인트와 개선 방향: while (sum >= m) 조건이 성립하려면 원소가 양수여야 합니다. 이 조건이 깨지면 lt를 움직인다고 해서 합이 안정적으로 줄어든다는 보장이 사라집니다. 즉, 문제 조건을 확인하지 않고 패턴만 적용하면 오답이 됩니다.
응용 예제: 정답 구간(인덱스)까지 함께 수집
function solutionWithRanges(m, arr) {
let count = 0;
let lt = 0;
let sum = 0;
const ranges = [];
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) {
count++;
ranges.push([lt, rt]);
}
while (sum >= m) {
sum -= arr[lt++];
if (sum === m) {
count++;
ranges.push([lt, rt]);
}
}
}
return { count, ranges };
}
console.log(solutionWithRanges(6, [1, 2, 1, 3, 1, 1, 1, 2]));동작 설명: 기본 풀이와 동일하게 구간을 유지하되, sum === m이 되는 순간마다 [lt, rt]를 저장합니다. 결과는 “경우의 수”와 “구간 목록”을 함께 반환합니다.
메커니즘 해설: while 내부에서 lt가 먼저 증가한 뒤 합을 검사하는 구조이기 때문에, 저장하는 인덱스는 항상 “현재 sum을 만드는 실제 구간”과 일치합니다. 이 부분에서 lt 증가 순서가 바뀌면 구간이 틀어지기 쉽습니다.
실수 포인트와 개선 방향: 구간을 많이 저장하면 메모리 사용량이 늘어납니다. 문제 요구가 경우의 수라면 저장을 생략하는 편이 합리적입니다. 반대로 학습/검증 단계에서는 구간이 실제로 맞는지 빠르게 확인할 수 있어 유용합니다.
오류 예제: 음수가 섞이면 투 포인터가 깨지는 이유
function slidingWindowCount(m, arr) {
let answer = 0;
let lt = 0;
let sum = 0;
for (let rt = 0; rt < arr.length; rt++) {
sum += arr[rt];
if (sum === m) answer++;
while (sum >= m) {
sum -= arr[lt++];
if (sum === m) answer++;
}
}
return answer;
}
console.log(slidingWindowCount(1, [1, -1, 1]));동작 설명: 위 코드는 양수 배열 기준으로는 잘 동작하지만, [1, -1, 1]처럼 음수가 섞이면 기대한 결과를 만들지 못합니다.
메커니즘 해설: 음수가 포함되면 구간을 확장했는데 합이 줄어들 수도 있고, 왼쪽을 줄였는데 합이 늘어날 수도 있습니다. 즉, “커졌으면 줄이면 된다”라는 단조성 기반 규칙이 깨집니다. 따라서 같은 코드라도 오답이 될 수 있습니다.
실수 포인트와 개선 방향: 투 포인터는 전제가 있는 기법입니다. “연속 구간 + 단조성(양수)”이 맞는지 먼저 확인해야 합니다. 전제가 깨지면 누적합 기반 해법으로 전환하는 편이 안전합니다.
개선 예제: 누적합 + 해시 맵(음수 포함 일반 케이스 대응)
function countSubarraysSumK(k, arr) {
let count = 0;
let prefix = 0;
const freq = new Map();
freq.set(0, 1);
for (const x of arr) {
prefix += x;
const need = prefix - k;
if (freq.has(need)) {
count += freq.get(need);
}
freq.set(prefix, (freq.get(prefix) || 0) + 1);
}
return count;
}
console.log(countSubarraysSumK(1, [1, -1, 1]));동작 설명: 누적합 prefix를 진행하면서, 현재 누적합에서 k를 뺀 값(prefix - k)이 이전에 몇 번 등장했는지를 더합니다. 그 횟수가 곧 “현재 위치에서 끝나는 정답 구간의 개수”입니다.
메커니즘 해설: 연속 구간 합은 누적합의 차이로 표현됩니다. prefix[i] - prefix[j] = k가 되려면 prefix[j] = prefix[i] - k가 필요합니다. 해시 맵에 누적합 빈도를 쌓아두면, 매 위치에서 필요한 과거 누적합의 개수를 O(1)에 조회할 수 있습니다.
실수 포인트와 개선 방향: 이 방식은 음수까지 포함해도 안정적이지만, 본 문제는 자연수 조건이 있으므로 투 포인터가 더 단순하고 직관적입니다. 즉, “전제가 맞으면 투 포인터, 전제가 깨지면 누적합+맵”으로 분기하는 판단이 중요합니다.
FAQ
Q. 이 문제에서 ‘연속 부분수열’은 정확히 무엇을 의미하나요?
연속 부분수열은 시작 인덱스와 끝 인덱스를 정하면 그 사이 원소를 모두 포함하는 구간을 의미합니다. 중간을 건너뛰는 선택은 허용되지 않습니다.
Q. O(n²) 풀이도 조기 종료를 넣으면 실전에서 충분하지 않나요?
평균적으로는 빨라질 수 있지만, 최악의 경우 O(n²) 자체는 변하지 않습니다. N이 100,000인 입력에서는 최악 케이스 한 번으로도 시간 제한을 넘기기 쉽기 때문에, 코테에서는 “최악 시간” 기준으로 판단하는 편이 안전합니다.
Q. 투 포인터가 가능한 핵심 조건을 한 문장으로 정리하면 무엇인가요?
배열 원소가 모두 양수라서, 구간을 확장하면 합이 증가하고 구간을 축소하면 합이 감소하는 단조성이 성립해야 합니다.
Q. 투 포인터 풀이가 O(n)이라는 것을 근거까지 포함해 설명해보세요.
rt는 0부터 N-1까지 한 번씩만 증가하고, lt도 0부터 N까지 한 번씩만 증가합니다. 각 원소는 한 번 더해지고 한 번 빠질 뿐이어서 전체 연산은 최대 2N에 비례합니다.
Q. 이 문제를 누적합 + 맵으로도 풀 수 있는데, 그럼 왜 투 포인터를 선호하나요?
자연수 조건에서는 투 포인터가 구현이 더 단순하고 메모리를 거의 쓰지 않습니다. 누적합+맵은 음수까지 대응 가능한 장점이 있지만, 본 문제에서는 불필요하게 구조가 커질 수 있습니다.
Q. 음수가 섞인 배열에서 ‘합이 M인 연속 부분수열 개수’는 어떤 전략이 안정적인가요?
단조성이 깨지므로 투 포인터만으로는 안정적으로 카운트하기 어렵습니다. 이때는 누적합과 해시 맵(누적합 빈도)을 사용해 O(n)으로 카운트하는 방식이 일반적으로 안전합니다.