코딩테스트 슬라이딩 윈도우 풀이: 최대 매출 구간 합 계산하기

내가 처음 작성한 풀이와 한계

문제를 처음 접했을 때, 가장 먼저 떠올린 방식은 시작 지점을 하나씩 옮기면서 K개의 값을 직접 더해보는 방법이었습니다. 실제로 이 방식으로 코드를 작성했고, 예제 입력에 대해서는 정답이 올바르게 출력되었습니다.

function solution(k, arr) {
  let result = 0;
  let start = 0;

  while (start <= arr.length - k) {
    let sum = 0;
    for (let i = 0; i < k; i++) {
      sum += arr[start + i];
    }
    result = Math.max(result, sum);
    start++;
  }

  return result;
}

이 코드가 헷갈리기 쉬운 이유는, “정답은 맞기 때문”입니다. 실제로 모든 연속된 K개의 구간을 빠짐없이 확인하기 때문에 논리적으로 틀린 풀이는 아닙니다.

하지만 문제의 핵심은 단순히 정답을 구하는 것이 아니라, 제한된 시간 안에 얼마나 효율적으로 계산할 수 있는지에 있습니다. 위 코드는 구간을 한 칸 이동할 때마다 항상 K개의 값을 다시 더합니다.

예를 들어 K가 3일 때, 첫 번째 구간과 두 번째 구간은 대부분의 값이 겹칩니다. 그럼에도 불구하고 이 풀이는 겹치는 값까지 매번 다시 계산합니다. 이로 인해 같은 숫자를 여러 번 반복해서 더하게 됩니다.

입력 크기 N이 커질수록 이 반복 계산은 급격히 늘어납니다. 문제 조건상 N은 최대 100,000까지 가능하기 때문에, 이러한 방식은 시간 제한에 걸릴 가능성이 높습니다.

즉, 이 풀이는 “틀린 풀이”라기보다는 “문제에서 요구하는 수준의 효율을 만족하지 못하는 풀이”입니다. 이 점을 인식하지 못하면, 왜 투 포인터를 써야 하는지 이해하기 어렵습니다.

투 포인터 풀이 구조

function solution(k, arr) {
  let sum = 0;

  // 초기 윈도우 합 만들기
  for (let i = 0; i < k; i++) {
    sum += arr[i];
  }

  let max = sum;

  // 슬라이딩 윈도우 이동
  for (let rt = k; rt < arr.length; rt++) {
    sum += arr[rt];      // 새로 들어오는 값
    sum -= arr[rt - k];  // 빠지는 값
    max = Math.max(max, sum);
  }

  return max;
}

이 문제에서 투 포인터(슬라이딩 윈도우)를 사용한다는 것은, 연속된 K개의 값을 하나의 “창문”처럼 보고 그 창문을 한 칸씩 이동시키며 합을 관리한다는 의미입니다. 핵심은 매번 전체를 다시 계산하지 않고, 이전 계산 결과를 그대로 활용하는 데 있습니다.

사고 흐름을 단계별로 나누면 이해가 훨씬 쉬워집니다.

1단계: 첫 번째 구간 만들기
먼저 배열의 앞에서부터 K개의 값을 더해 최초의 구간 합을 만듭니다. 이 값은 이후 모든 비교의 기준이 됩니다.

let sum = 0;
for (let i = 0; i < k; i++) {
  sum += arr[i];
}
let max = sum;

이 시점에서 sum은 0번 인덱스부터 K-1 인덱스까지의 합을 의미합니다. 즉, 현재 윈도우는 [0 ~ K-1] 구간에 놓여 있습니다.

2단계: 창문을 한 칸씩 이동시키기
이제 구간을 한 칸 오른쪽으로 이동합니다.
이때 기존에 계산해 둔 sum 값에 새로 들어오는 값은 더하고, 구간에서 빠지는 값은 빼주기만 하면 됩니다.
그래서 매번 처음부터 다시 합을 구할 필요가 없습니다.

따라서 새로운 구간을 만들기 위해 필요한 작업은 단 두 가지입니다.

• 새로 포함되는 값 하나를 더한다
• 구간에서 빠지는 값 하나를 뺀다

for (let rt = k; rt < arr.length; rt++) {
  sum += arr[rt];      // 새로 들어오는 값
  sum -= arr[rt - k];  // 구간에서 빠지는 값
  max = Math.max(max, sum);
}

여기서 rt는 항상 현재 구간의 오른쪽 끝을 가리킵니다. rt – k는 이번 이동에서 빠지는 이전 창의 왼쪽 값입니다. 추가·제거 후 현재 창의 왼쪽 끝은 rt – k + 1입니다. 이 점이 투 포인터 풀이를 간결하게 만드는 핵심입니다.

3단계: 왜 이 방식이 빠른가
각 반복에서 수행되는 연산은 덧셈 1번, 뺄셈 1번뿐입니다. 따라서 배열을 한 번만 순회하게 되고, 전체 시간 복잡도는 O(N)이 됩니다.

반면 이전 풀이처럼 매번 K개의 값을 다시 더하는 방식은, 같은 숫자를 계속 반복해서 계산하게 되어 입력이 커질수록 성능 차이가 크게 벌어집니다.

정리하면, 투 포인터 풀이의 본질은 “포인터를 움직이는 기술”이 아니라 이미 계산한 결과를 다시 쓰는 사고 방식입니다. 이 관점이 잡히면 비슷한 유형의 문제에서도 자연스럽게 슬라이딩 윈도우를 떠올릴 수 있습니다.

입력 배열과 계산용 공간

본문의 완성 함수는 이미 주어진 N개 매출 배열을 읽고 sum, max, 인덱스만 유지하므로 입력을 제외한 추가 공간은 O(1)입니다. 최대 합 숫자 하나를 반환하므로 출력도 O(1)입니다. 입력 배열까지 포함한 저장 공간은 O(N)이며, 표준 입력 문자열을 배열로 변환해 호출할 때는 그 문자열·토큰·배열의 저장도 포함해야 합니다. 매 이동마다 새 구간 배열을 만드는 코드는 아닙니다.

비교 정리 및 선택 기준

연속된 구간 + 고정 길이라는 조건이 보이면, 브루트포스보다 투 포인터를 우선적으로 떠올리는 것이 좋습니다. 아직은 자연스럽지 않지만, 이런 유형을 반복해서 풀어보며 익숙해질 필요가 있다고 느꼈습니다.

투 포인터 기본형을 함께 복기하려면 JS 연속 구간 합 투 포인터를 먼저 다시 보시면 좋습니다.

배열의 연속 구간 합 구조 확장은 JS 연속부분수열 투 포인터에서 변형 형태로 이어집니다.