[알고리즘] Sliding Window Pattern 심화

 

sliding window pattern을 이해하기 위한 좋은 예제

function minSubArrayLenSol(nums, sum) {
  let total = 0; // 들어온 sum과 비교할 window 내 값들의 합을 담아줄 total
  let start = 0; // window의 시작 index
  let end = 0; // window의 끝 index
  let minLen = Infinity; // return 해 줄 가장 짧은 window 길이. 어떤 길이여도 가장 처음 길이가 min이 되도록 Infinity로 입력

  while (start < nums.length) { // window가 nums array를 벗어날 때까지
    if (total < sum && end < nums.length) { // window 내 값들 합이 들어온 sum보다 작고 window의 end가 array 안에 있을 때
      total += nums[end]; // total은 더해주고
      end++; // window의 크기를 키운다(end가 커지면 window가 커진다)
      console.log(
        `window increase: ${nums.slice(start, end)}\nlength: ${
          nums.slice(start, end).length
        }`
      );
    }
    else if (total >= sum) { // window 내 합이 입력된 sum보다 크면 조건에 부합
      console.log(`over ${sum}: ${nums.slice(start, end)}`); 
      minLen = Math.min(minLen, end - start); // minLen과 현재 window의 길이 중 더 짧은 값 넣어주기
      total -= nums[start]; // window내 합들이 sum을 벗어나므로 현재 window start 값을 빼주고
      start++; // window 크기를 줄인다.
      console.log(
        `window decrease: ${nums.slice(start, end)}\nlength: ${
          nums.slice(start, end).length
        }`
      );
    }
    else {
      break;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

주석달린 대로의 설명을 console로 출력해서 보면 다음과 같다.

console.log(
  minSubArrayLenSol([1, 2, 5, 3, 7, 89, 3, 1, 5, 65, 1, 56, 1, 5, 6, 23], 100)
);

window increase: 1
length: 1
window increase: 1,2
length: 2
window increase: 1,2,5
length: 3
window increase: 1,2,5,3
length: 4
window increase: 1,2,5,3,7
length: 5
window increase: 1,2,5,3,7,89
length: 6
over 100: 1,2,5,3,7,89
window decrease: 2,5,3,7,89
length: 5
over 100: 2,5,3,7,89
window decrease: 5,3,7,89
length: 4
over 100: 5,3,7,89
window decrease: 3,7,89
length: 3
window increase: 3,7,89,3
length: 4
over 100: 3,7,89,3
window decrease: 7,89,3
length: 3
window increase: 7,89,3,1
length: 4
over 100: 7,89,3,1
window decrease: 89,3,1
length: 3
window increase: 89,3,1,5
length: 4
window increase: 89,3,1,5,65
length: 5
over 100: 89,3,1,5,65
window decrease: 3,1,5,65
length: 4
window increase: 3,1,5,65,1
length: 5
window increase: 3,1,5,65,1,56
length: 6
over 100: 3,1,5,65,1,56
window decrease: 1,5,65,1,56
length: 5
over 100: 1,5,65,1,56
window decrease: 5,65,1,56
length: 4
over 100: 5,65,1,56
window decrease: 65,1,56
length: 3
over 100: 65,1,56
window decrease: 1,56
length: 2
window increase: 1,56,1
length: 3
window increase: 1,56,1,5
length: 4
window increase: 1,56,1,5,6
length: 5
window increase: 1,56,1,5,6,23
length: 6
3

결국 array를 바라보는 window, 프레임을 1. 늘리고 줄여가며 2. 이동하며 바라본다.