Sliding window

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.

 

이 패턴은 한 위치에서 다른 위치로 배열 또는 숫자가 될 수 있는 창을 만드는 것을 포함합니다. 특정 조건에 따라 창이 커지거나 닫힙니다(새 창이 생성됨). 배열/문자열에 있는 데이터의 하위 집합을 추적하는 데 매우 유용합니다.

 

Write a function call maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

 

정수 배열과 n이라는 숫자를 허용하는 함수 호출 maxSubarraySum을 작성하십시오. 함수는 배열에 있는 n개의 연속 요소의 최대 합을 계산해야 합니다.(배열 안의 숫자는 정렬이 되어 있지 않음)

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

방법

보통 이 창문은 왼쪽-> 오르쪽으로 가지만 오르쪽->왼쪽일수도 있고, 가운데에서 시작할수도 있다.

 

비효율적인 해결

Time complexity - O(N^2)

//not really good way

function maxSubarraySum(arr, num) {
  if (num > arr.length) {
    return null;
  }

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

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

 

이 방법에서는 nested loop이 있어서 데이터가 길어지면 정말 비효과적이고 느려짐

 

Infinity

let max = 0;을 하지 않은 이유는 배열 안에 있는 모든 수가 음수일 경우 maxSubarraySum은 음수가 되어야 하는데 max값을 0으로 해놓으면 항상 max가 0으로 리턴되기 때문에 정답을 구할 수 없다. 

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

 

Sliding window를 활용한 해결

Time complexity - O(N)

 

//sliding window. 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;
}

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

 

이 줄이 sliding window의 핵심

    tempSum = tempSum - arr[i - num] + arr[i];

항상 temp이나 구하려는 값을 변수로 선언할 때 0으로 선언하는 이유는, 우선 숫자임을 보여주기 위함이고, 임시값인 0이 가장 안전하기 때문인 것 같다.

 

*더하기 할당 Addition assignement(+=)

MDN | 더하기 할당

더하기 할당 연산자(+=)는 오른쪽 피연산자의 값을 변수에 더한 결과를 다시 변수에 할당합니다. 두 피연산자의 타입이 더하기 할당 연산자의 동작을 결정하며, 덧셈 또는 문자열 연결이 가능합니다.

x += y // x = x + y

 

maxSum += arr[i] // maxSum = maxSum + arr[i]