[JS 알고리즘] 최대 매출 문제 풀이 – 투 포인터 알고리즘(5)

• 문제 설명
• 내가 처음 작성한 풀이와 한계
• 투 포인터 풀이 구조
• 비교 정리 및 선택 기준

문제 설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고, 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같다면, 이때 K=3이면

12 15 11 20 25 10 20 19 13 15

연속된 3일간의 최대 매출액은 11 + 20 + 25 = 56 만원입니다.

여러분이 현수를 도와주세요.

입력 설명
첫 줄에 N(5 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500 이하의 음이 아닌 정수입니다.

출력 설명
첫 줄에 최대 매출액을 출력합니다.

입력 예제

3
12 15 11 20 25 10 20 19 13 15

출력 예제

56

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

문제를 처음 접했을 때, 가장 먼저 떠올린 방식은 시작 지점을 하나씩 옮기면서 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로 자동 계산됩니다. 이 점이 투 포인터 풀이를 간결하게 만드는 핵심입니다.

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

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

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

비교 정리 및 선택 기준

구분	특징
브루트포스	구현은 쉽지만 중복 계산이 많음
투 포인터	이전 결과를 재사용하여 효율적

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

FAQ

Q. 이 문제는 어떤 키워드에서 투 포인터를 떠올려야 하나요?
연속 구간, 고정 길이, 최대 합 같은 조건이 함께 나오면 슬라이딩 윈도우를 의심해볼 수 있습니다.

Q. 투 포인터 풀이가 항상 더 좋은가요?
대부분 효율적이지만, 조건이 맞지 않으면 오히려 코드가 복잡해질 수 있어 문제 특성을 먼저 판단해야 합니다.

Q. 이런 문제를 빠르게 구분하는 연습 방법은?
문제를 읽을 때 길이가 고정된 연속 구간인지 먼저 체크하는 습관이 도움이 됩니다.