2.3Sliding Window

Sliding Window

Sliding Window(슬라이딩 윈도우) 패턴은 배열이나 문자열과 같은 연속된 데이터 구조에서 일정한 길이의 서브셋(부분 집합)을 추적하거나 계산하는 문제에서 사용된다.
보통 두 개의 인덱스 또는 범위를 사용하여 윈도우(window)를 형성하고, 이 윈도우를 한 칸씩 슬라이딩하면서 전체 데이터에 대한 반복 연산을 피할 수 있다.

• 윈도우는 고정 길이일 수도 있고, 조건에 따라 늘어나거나 줄어드는 가변 길이일 수도 있다.
• 시간 복잡도를 O(n²) → O(n)으로 줄이는 데 매우 효과적이다.

예시 1: maxSubarraySum

정수로 이루어진 배열과 정수 n이 주어졌을 때, 배열에서 연속된 n개의 요소의 최대 부분합을 구하라.

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

다음은 비효율적인 접근이다. 부분합들을 계산하며 그때까지 찾은 가장 큰 부분합을 저장해두고 비교하는 방식이다.

javascript
function maxSubarraySum(arr, num){
  if(num > arr.length){
    return null;
  }
  const 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;
}

다음은 Sliding Window를 이용한 풀이다. 첫 n개의 합을 초기값으로 설정한 후, 앞의 값을 빼고 새로운 값을 더하는 방식으로 윈도우를 이동한다.

javascript
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;
}

예시 2: minSubArrayLen 🎯

양수인 정수들로 구성된 배열과 양수인 정수, 두 개의 파라미터를 받아 전자(배열)의 요소들의 연속된 합으로 후자(양수인 정수)보다 큰 수를 만든다고 할 때 필요한 최소한의 요소 수를 구하는 minSubArrayLen 함수를 작성하라. 만약 모두 더해도 넘을 수 없다면 0을 반환한다.

• 시간 복잡도 제한: O(n)
• 공간 복잡도 제한: O(1)

javascript
minSubArrayLen([2,3,1,2,4,3], 7) // 2 -> because [4,3] is the smallest subarray
minSubArrayLen([2,1,6,5,4], 9) // 2 -> because [5,4] is the smallest subarray
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1 -> because [62] is greater than 52

모범 답안은 아래와 같다. Sliding Window 패턴의 알고리즘은 window를 우선 최소한으로(start와 end 인덱스를 모두 0으로 한다거나 해서) 설정하고 end를 늘리고 start를 늘리고 하는 식으로 조정하며 해결한다.

javascript
function minSubArrayLen(nums, sum) {
  let total = 0;
  let start = 0;
  let end = 0;
  let minLen = Infinity;
 
  while (start < nums.length) {
    // if current window doesn't add up to the given sum then 
		// move the window to right
    if(total < sum && end < nums.length){
      total += nums[end];
			end++;
    }
    // if current window adds up to at least the sum given then
		// we can shrink the window 
    else if(total >= sum){
      minLen = Math.min(minLen, end-start);
			total -= nums[start];
			start++;
    } 
    // current total less than required total but we reach the end, need this or else we'll be in an infinite loop 
    else {
      break;
    }
  }
 
  return minLen === Infinity ? 0 : minLen;
}

예시 3: findLongestSubstring 🎯

문자열을 입력받아 서로 다른 문자로 구성된 가장 긴 연속된 문자열의 길이를 반환하는 함수를 작성하라.

javascript
function findLongestSubstring(str) {
  let longest = 0;
  let seen = {};
  let start = 0;
 
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (seen[char]) {
      start = Math.max(start, seen[char]);
    }
    // index - beginning of substring + 1 (to include current in count)
    longest = Math.max(longest, i - start + 1);
    // store the index of the next char so as to not double count
    seen[char] = i + 1;
  }
  return longest;
}

나는 이렇게 풀었다. 거의 비슷한데, 인덱스를 어디서 보정하는지 정도만 차이가 났다.

javascript
function findLongestSubstring(str){
  const seen = {};
  let longest = 0;
  let start = 0;
  for (let end = 0; end < str.length; end++) {
    const char = str[end];

    if (seen[char] !== undefined) {
      // 중복이 발견되었으면 start를 점프
      start = Math.max(start, seen[char] + 1);
    }

    // 길이 갱신
    longest = Math.max(longest, end - start + 1);

    // 현재 문자 위치 저장
    seen[char] = end;
  }
    return longest;
}