서로 마주한 숫자들의 가장 큰 합계, 그리고 슬라이딩 윈도우 패턴

문제 설명

배열과 숫자 하나를 전달받는 maxSubarraySum 함수는 서로 마주한 두 숫자의 가장 큰 합계를 찾아서 반환한다. 빈 배열을 전달받을 경우 null을 반환한다.

인풋 예시는 다음과 같다.

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

위 예시중 두번째의 경우는 숫자 4를 넘겨줬다. 이는 즉 서로 마주한 네 숫자의 합이 가장 큰 합계를 반환해야 한다.
첫 번째 예시 또한 서로 마주한 두 숫자의 합이 가장 큰 합계를 반환해야 하고, 이는 2와 8의 합이므로 10을 반환한다.

이러한 문제는 슬라이딩 윈도우 패턴을 이용하면 비교적 쉽게 접근이 가능하다.
슬라이딩 윈도우 패턴이라는 것은 말 그대로 가상의 창문을 만들고 이를 인덱스를 따라 이동하면서 비교하는 패턴이다.
보통 창문의 이동 방향은 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동한다.
그리고 때에 따라서는 새로운 창문을 추가적으로 만들기도 한다.

이러한 슬라이딩 윈도우 패턴은 규모가 큰 데이터셋에서 하위 집합을 추적하는 문제에 있어서 유용하다.

다시 문제로 돌아가보자.

소스 코드

첫 번째 소스 코드

function maxSubarraySum(arr, num) {
 // 숫자가 배열의 길이보다 큰지를 확인하고 만약 크다면 null을 리턴한다.
 if (num > arr.length) {
  return null; 
 }
 // 배열이 모두 음수로 구성되어 있다면 가장 큰 합은 여전히 음수일 것을 예방한다.
 let max = -Infinity;
 // 이 루프는 배열의 끝이나 거의 끝까지 도달한다. 루프가 n의 값에 따라서 배열의 끝까지 도달할 필요가 없으며, 결국 arr.length - num의 위치가 합계를 구할 수 있는 마지막 위치이므로 다음과 같이 설정한다. 
 for (let i = 0; i < arr.length - num; i++) {
  // temp 에는 각 루프를 돌며 max와 값을 비교하고 큰 값을 저장한다. 
  let temp = 0; 
  for (let j = 0; j < num; j++) {
   temp += arr[i + j]; 
  }
  // num이 3일 경우라면, 3개의 연속된 숫자를 더한 값을 temp에 저장하고 max와 비교해준다. 만약 temp가 더 크다면 max를 현재의 temp 값으로 바꾼다. 맨 처음 루프가 수행될 때 max는 -Infinity이다. 따라서 어떤 작업을 하든 max 는 새로운 숫자로 갱신된다.
  if (temp > max) {
   max = temp; 
  }
 }
 return max;
};

위 소스코드의 시간복잡도는 O(n^2) 이다. 중첩된 루프는 막대한 비효율성을 야기할 수 있다.

• 위에서 max를 -Infinity로 초기화해놓은 것에 대한 추가 설명 :
  배열이 모두 음수로 구성되어 있다면 가장 큰 합은 여전히 음수일 것이다. 이는 곧 양수로만 작업 하는 것이 아닌 한 max를 0에서 시작하는 것은 전혀 도움이 되지 않음을 뜻한다. 따라서 max를 -Infinity로 초기화한다.

리팩토링 소스 코드

function maxSubarraySum(arr, num) {
 let maxSum = 0;
 let tempSum = 0;
 if (arr.length < num) return null;
 for (let i = 0; i < num; i++) {
  // maxSum에 밑의 합계(n개의 연속된 숫자들의 합)를 지니도록 유지시킨다.
  maxSum += arr[i]; 
 };
 // 현재 상태의 maxSum의 값을 tempSum에 저장한다.
 tempSum = maxSum;
 // 새로운 루프를 만든다.
 for (let i = num; i < arr.length; i++) {
  // 기존의 연속된 숫자들 중에서 제일 좌측의 숫자를 빼주고, 대신 제일 우측의 숫자에서 하나 더 우측인 숫자를 더해준다.
  tempSum = tempSum - arr[i - num] + arr[i];
  // tempSum과 maxSum 중 큰 값을 다시 maxSum에 재할당해준다.
  maxSum = Math.max(maxSum, tempSum);
 };
 return maxSum;
};

maxSubarraySum([2,6,9,2,1,8,5,6,3], 3); // 19

위 소스코드의 시간복잡도는 O(n)이며 슬라이딩 윈도우 패턴의 예시이다.
두 개의 루프가 입력되어 있지만 배열 전체에 루프는 한 번만 적용된다.

• 추가 설명 :
  만약 주어진 배열이 [1, 2, 3, 4, 5, 6, 7] 이고 주어진 숫자는 3이라면 우리는 1 + 2 + 3을 하고, 그 다음에는 2 + 3 + 4를 해나가게 될 것이다.
  여기에서 우리의 함수는 굳이 매번 연속된 숫자들의 합을 구할 필요가 없다.
  그저 1 + 2 + 3 에서 1만 빼주고 원래의 가장 우측의 숫자였던 3에서 하나 더 우측에 있는 숫자인 4를 더해주면 되는 것이다.

즉 1 + 2 + 3 에서 1을 빼주고 4를 1 대신 우측에 추가해준 뒤 연속된 세 개의 합을 파악하는 로직이다. 이것이 슬라이딩 윈도우의 기능이며 훨씬 효율적인 방법이다.