[JS] 윈도우 슬라이딩 기법

코딩테스트를 풀 때 우리는 최대한 시간복잡도 면에서 n^2은 지양해야 할 부분이 많다. 그저 어쩌다 풀다보면 중첩 for문을 돌리고 있는 우리를 볼 수 있다. 이때 O(N)의 시간복잡도로 풀 수 있는 다양한 매커니즘이 있는데 이를 소개하고자 한다.

1. 해당 함수에는 두개의 인자가 주어지는데, 하나는 숫자가 담긴 배열이고 두번째는 특정 숫자이다. 당신은 첫번째로 주어진 배열에서 가장 적은, "연속된" 요소를 조합해 특정 숫자와 같거나 높게 만들어야 한다. 배열에서 가장 적은 요소를 사용할 때, 그 요소의 개수는 몇 개인가?

minSubArrayLen([2,3,1,2,4,3], 7) // 2
minSubArrayLen([2,1,6,5,4], 9) // 2
minSubArrayLen([3,1,7,11,2,9,8,21,62,33,19], 52) // 1
minSubArrayLen([1,4,16,22,5,7,8,9,10],39) // 3
minSubArrayLen([1,4,16,22,5,7,8,9,10],55) // 5
minSubArrayLen([4, 3, 3, 8, 1, 2, 3], 11) // 2
minSubArrayLen([1,4,16,22,5,7,8,9,10],95) // 0

쉬워보일 수 있지만, 사실 연속된 것 중이기 때문에 섣불리 sort를 통해 유추해낼 수 없다.
가장 쉽게 생각해낼 수 있는 것은 조합을 1개부터 배열의 숫자까지 늘려나가는 것이다. 그리고 타겟넘버에 해당하는 조합이 나오는 경우 해당 조합의 요소 길이를 반환하면 된다. 하지만 이러면 최악의 경우 n+(n-1)+(n-2)...+1의 시간복잡도가 소요되므로 사실상 O(n^2)이 소요된다.

이때 창문을 열 듯이, 즉 앞과 뒤의 인덱스를 빼가며 계산을 해볼 수 있다.

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

해당 경우는 앞에서부터 더해가며, 타겟넘버와 같거나 높은 숫자가 되었을 경우 그 이전에 있었던 배열의 길이와 비교를 한다. 그리고 마지막에 해당 배열이 타겟넘버 이상이 되지 못했을 때를 대비해 예외처리를 해준다.
앞의 인덱스를 제거하고 뒤의 인덱스를 더해가는 장면이 마치 창문을 옆으로 미는 것과 같다고 하여 붙여진 매커니즘인 듯 하다. 해당 코드의 시간복잡도는 코드의 정렬도에 따라 다르겠지만 그래도 절대적인 O(N)의 시간복잡도가 소요된다.

문제 출처 : https://www.udemy.com/course/best-javascript-data-structures