[JS 알고리즘&자료구조] 기준점과 이동 배열 패턴

기준점과 이동 배열 패턴은 '슬라이딩 윈도우 패턴' 이라고도 부르며 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 큰 데이터셋에 하위 집합을 찾을 때 유용하다.

아래는 기준점과 이동 배열 패턴을 사용하여 해결할 수 있는 문제이다.

/*
maxSubarraySum이라는 함수가 있다. 
이 함수는 배열과 숫자 하나를 매개 변수로 받으며 받은 숫자 만큼 연속된 숫자들의 가장 큰 합계를 찾는 함수이다. 
아래는 함수의 반환값들의 예시이다.
*/

maxSubarraySum([1,2,5,2,8,1,5], 2) // 10
maxSubarraySum([1,2,5,2,8,1,5], 4) // 17
maxSubarraySum([4,2,1,6], 1) // 6
maxSubarraySum([4,2,1,6,2], 4) // 13
maxSubarraySum([], 4) // null

문제를 해결하기 위해 우리는 우선 '창문'(윈도우)를 만들어야 한다. 창문은 단일 변수, 하위 배열 혹은 문자열이 될 수 있다. 이 창문을 조건에 따라 특정 방향으로 진행시키며 원하는 값을 찾아낸다. 우선 패턴을 사용하지 않는 풀이법부터 살펴보자.

function maxSubarraySum(arr, num) {
  if (num > arr.length) {
    return null;
  }
  
  let max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++) {
    temp = 0;
    for (let j = 0; j < num; j++) {
      temp += arr[i+j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  
  return max;
}

위의 방법은 당연히 배열이 작을 때는 문제가 없으나 배열이 커지는 순간 엄청나게 큰 처리 속도를 가지게 된다. 빅오 표기법으로도 O(n²)의 시간 복잡도를 가지게 된다. 이제 슬라이딩 윈도우 패턴을 사용하여 위의 로직을 리팩토링해보자.

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
  	maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

위의 방법을 통해 원래는 반복문을 계속 돌면 num 만큼을 반복하여 합산을 진행해야했지만 이제는 맨 앞 인덱스에 있는 숫자를 빼고 마지막 인덱스의 다음 인덱스에 있는 숫자를 더하는 간단한 작업만으로 합산을 계속 비교해가면서 진행해나갈 수 있게 되었다. 이를 통해 우리는 O(n)의 시간 복잡도를 가진 로직으로 리팩토링도 성공적으로 수행해낸 것이다.