합이 특정 숫자와 같은 모든 부분 배열 찾기 — JavaScript 슬라이딩 윈도우 알고리즘

숫자로 이루어진 배열과 하나의 숫자가 주어졌을 때, 두 번째 인자로 전달된 값과 합이 일치하는 모든 부분 배열(subarray)을 담은 배열을 반환하는 함수를 작성하는 것이 이번 글의 목표입니다.

예를 들어 다음과 같습니다.

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
console.log(requiredSum(arr, sum));

위 코드는 아래와 같은 배열을 출력해야 합니다.

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]

이 세 개의 부분 배열은 각각의 합이 모두 40이 되기 때문입니다.

슬라이딩 윈도우 알고리즘(선형 시간)

슬라이딩 윈도우(Sliding Window) 알고리즘은 주로 배열 안에서 특정 조건을 만족하는 부분 배열을 찾거나, 문자열 안에서 조건에 맞는 부분 문자열을 구해야 할 때 활용됩니다. 그리고 이 문제는 슬라이딩 윈도우 알고리즘을 적용하기에 완벽한 예시입니다.

슬라이딩 윈도우 알고리즘은 이름 그대로, 원본 배열의 일부인 부분 배열을 하나의 '윈도우(창)'로 취급합니다. 이 윈도우는 크기를 늘리거나 줄이며 안정 상태에 도달하려고 시도합니다.

여기서 '안정'이란 문제에서 요구하는 조건(이 문제에서는 합이 특정 숫자와 일치하는 것)을 충족하는 상태를 의미합니다. 안정 상태에 도달하면 해당 윈도우를 기록하고, 계속해서 윈도우를 밀어 나갑니다. 일반적으로 대부분의 문제에서는 윈도우를 왼쪽에서 시작해 오른쪽 끝이 배열이나 문자열의 끝에 도달할 때까지 이동시키는 방식을 사용합니다.

이러한 방식 덕분에 시작 포인터와 끝 포인터가 각각 배열을 최대 한 번씩만 순회하므로, 전체 시간 복잡도는 O(n)의 선형 시간이 됩니다. 중첩 반복문으로 모든 부분 배열을 확인하는 O(n²) 방식보다 훨씬 효율적입니다.

이제 코드를 살펴보며 슬라이딩 윈도우 알고리즘에 더 익숙해져 보겠습니다.

예시 코드

const arr = [23, 5, 1, 34, 12, 67, 9, 31, 6, 7, 27];
const sum = 40;
const findSub = (arr, sum) => {
   const required = [];
   for(let start = 0, end = 0, s = 0; end <= arr.length || s > sum ; ){
      if(s < sum){
         s += arr[end];
         end++;
      }else if(s > sum){
         s -= arr[start];
         start++;
      }else{
         required.push(arr.slice(start, end));
         s -= arr[start];
         s += arr[end];
         start++;
         end++;
      };
   };
   return required;
};
console.log(findSub(arr, sum));

start와 end 변수는 각 시점에서 윈도우의 시작 위치와 끝 위치를 나타냅니다.

처음에는 두 변수 모두 0에서 시작합니다. 이후 현재 합이 목표 합보다 작으면 윈도우 크기를 늘리고, 크면 윈도우 크기를 줄입니다. 그리고 어느 시점에서 합이 정확히 일치하면 해당 부분 배열을 required 배열에 저장한 뒤, 윈도우를 오른쪽으로 한 칸 이동시켜 다음 후보를 탐색합니다.

출력 결과

이 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.

[ [ 5, 1, 34 ], [ 9, 31 ], [ 6, 7, 27 ] ]