[알고리즘 | JS] Sliding Window Pattern(기준점 간 이동 배열 패턴)

🍕Sliding Window 패턴이란? 

-This pattern involves creating a window which can either be an array or number from one position to another.
-Depending on a certain condition, the window either increases or closes(and a new window is created)
-very useful for keeping track of a subset of data in an array/string etc... 

• 배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용하다. (규모가 큰 데이터 셋에서 데이터의 하위 집합을 추적하는 문제에 있어서 유용)
• 해당 패턴은 창문(window)을 하나 만들어야 하는데 이 창문은 단일 변수, 하위 배열 또는 필요한 경우 문자열이 될 수도 있다. 
• 조건에 따라 창문을 이동시키며, 시작 위치는 보통 왼쪽 -> 오른쪽으로 이동( 보통, 창문(window)을 왼쪽 즉, 요소의 시작 위치, 또는 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동 )한다.
• 반대로 오른쪽 -> 왼쪽으로 이동도 가능하며 중앙에서 시작하는 것도 가능하다. 

예시를 통해서 알아보자.

An Example
인자(param)로 정수 배열과 n이라는 수를 취하는 maxSubarraySum 이라는 함수를 작성해라
-배열은 정렬할 필요없이 '정수'만 있으면 된다. (정렬 필요없음)
-두 번째 인자인 n을 전달하면 함수는 해당 배열의 연속된 요소의 가장 큰 합계를 계산하게 된다. 
*n은 합계를 구하고자 하는 숫자의 개수
maxSubarraySum([1,2,4,2,8,1,5], 2) //10 
위의 예시 코드를 설명하면, 2개의 연속된 값의 합이 가장 큰 것을 찾는 것 즉, 2,8의 합이 제일 크므로 10을 반환

 

▶naive solution 의 경우, 시간 복잡도: O(n^2)

/*
the result should be...
maxSubarraySum([1,2,4,2,8,1,5],2) //10
maxSubarraySum([1,2,5,2,8,1,5],4) //17
maxSubarraySum([4,2,1,6],1) //10
maxSubarraySum([4,2,1,6,2],4) //13
maxSubarraySum([], 4) // null
*/

//먼저 naive solution (비효율적이지만 작동은 하는 순진한 접근법)
//이중 for문으로 시간 복잡도는 O(n^2)임
//n은 합계를 구하고자 하는 숫자의 개수
function maxSubarraySum(arr, num) {
  if (num > arr.length) {
    return null;
  }
  //배열이 모두 음수로 구성되어 있다면 가장 큰 합은 여전히 음수일 것임
  //이처럼 양수로만 작업을 하지 않는한 0에서 시작하는 것은 전혀 도움이 되지 않기 때문에
  //0대신 -infinity로 설정한 것이다.
  let max = -Infinity;
  //i가 순회하는 범위는 배열의 끝까지 도달하는 것이 아니라 -num + 1을 한다.
  for (let i = 0; i < arr.length - num + 1; i++) {
    //temp에는 각 루프의 합계가 저장된다.
    //n개의 수를 더해서 현재의 max보다 크다면 max가 temp가 되도록 바꿔준다.
    let temp = 0;
    for (let j = 0; j < num; j++) {
      //arr[i + j]는, i에서 시작하여 i + j를 수행하면 j의 위치(index)가 옆으로 한 자리 이동하는데,
      //num이 3일때, 세 가지 숫자를 더하는 방법이라고 보면 된다.
      //그냥 단순하게 생각하면 2중 for 문이니까 i가 한번 카운트되면,
      //j라는 변수가 index를 3개 순회하면서 그 값을 temp에 더하는 것
      temp += arr[i + j];
    }
    //만일 temp가 max보다 큰 경우에 max가 temp와 같도록 해준다.
    if (temp > max) {
      max = temp; // 새 값으로 max를 바꾸는 것(현재 값보다 더 큰 값을 만났으니 update)
    }
    //결과값을 확인해보기위해 콘솔로그
    console.log(temp, max);
  }
  return max;
}
console.log(maxSubarraySum([2, 3, 64, 5, 2, 4, 1], 3));
/*
풀이: 
n이 3일 때,
아래와 같이 3개를 연산하여 합계를 냄
2, 3, 64 = 69 max는 69
3, 64, 5 = 72 max는 72
64, 5, 2 = 71 max는 이전값 그대로 72
5, 2, 4 = 11 max는 그대로 72
2, 4, 1 // 여기서 '2'가 마지노선으로 3개를 연산할 수 있는 곳이 되므로 arr.length - num(3) + 1
// 7 max는 그대로 72

temp, max
69 69
72 72 
71 72 
11 72
7 72
결과: 72
*/

 

코드 해설

• 맨 처음 if절은 num이 배열의 길이를 넘어가는 경우 null을 반환하도록 하여 입력값에 제한을 둔다.
• let max = - Infinity; 코드는 배열의 모든 값이 음수로 구성되어 있다면 가장 큰 합이 여전히 음수일 것을 고려하여 세팅한 것 배열에 모든 값들이 양수가 아닌 이상 초기값을 0으로 설정하는 것은 도움이 되지 않는다.
• arr.length -num + 1 i가 순회하는 범위는 배열의 끝까지 도달하는 것이 아니라 num에 해당하는 값 + 1이다. 예로 n이 3이라면 3가지 값을 더해야하기 때문에 최대로 도달할 수 있는 곳이 '배열전체길이' - 3 + 1 이 되는 것이다. 
• let temp = 0; temp는 n개의 값을 더한 값이 들어가는 공간이다. 0으로 초기화해준다.
• 내부 for문 (let j = 0; j < num; j++){ //중략 } 3개의 값을 차례대로 더하여 temp에 담아주는 작업을 한다.
• if(temp > max) { max = temp;} temp가 max보다 큰 경우에 max의 값을 temp의 값으로 업데이트해준다. 
• for문을 빠져나오면 return max 를 통해 가장 큰 값을 함수의 결과값으로 리턴해준다. 

---

▶위의 코드를 리팩토링한 코드( 슬라이딩 미러 패턴을 적용) 

-시간 복잡도가 O(n^2) -> O(n) 선형타임으로 된다. 

function reFMaxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  //합계가 유효하지 않은 배열이고 숫자가 너무 크면 null 반환
  if (arr.length < num) return null;
  //첫번째 maxSum을 만든다.
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    //아래의 코드가 sliding window 패턴적용: 배열 값에 하나를 빼고 하나를 더하는 것
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum); // Math.max()는 더 큰 값을 취하는 메소드이다.
    //naive solution처럼 if문을 사용해도된다.
    //tempSum이 maxSum보다 크면 maxSum을 갱신해준다.
    console.log(tempSum, maxSum);
  }
  return maxSum;
}
reFMaxSubarraySum([2, 3, 4, 51, 5, 2, 3, 6, 5], 3);
console.log(reFMaxSubarraySum([2, 3, 4, 51, 5, 2, 3, 6, 5], 3));

슬라이딩 윈도우 패턴 설명