js - 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)는 배열이나 문자열에서 연속된 범위(부분 구간)를 한 칸씩 옮겨가며 검사하는 기법입니다.

일정한 범위를 유지하면서 한 칸씩 앞으로 이동하므로 O(n) 시간복잡도로 문제를 효율적으로 해결할 수 습니다..

---

✅ 슬라이딩 윈도우 방식이란?

• 기존 방식 (slice 사용)
  → 매 반복마다 slice(ex : discount.slice(i, i + 10))를 새로 만들어서 처리 → 시간 복잡도 O(n * 10) (즉, 전체 탐색 n번 * 슬라이스 10)
• 슬라이딩 윈도우 방식
  → 초기 윈도우 한번 만들고, 다음 윈도우는 앞 원소 빼고, 뒤 원소 추가하는 식으로 처리 → 시간 복잡도 O(n) 근접

---

✨ 문법 구조 요약

for (let i = 0; i < windowSize; i++) {
  // 초기 윈도우 상태 구성
}

for (let i = windowSize; i < arr.length; i++) {
  // 1. 이전 요소 제거
  // 2. 새로운 요소 추가
  // 3. 윈도우 조건 검사
}

 

---

✨ 예시

 

const arr = [1, 2, 3, 4, 5];
const k = 3;

let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i]; // 초기 윈도우

let maxSum = sum;

for (let i = k; i < arr.length; i++) {
  sum += arr[i] - arr[i - k]; // 한 칸 밀면서 상태 갱신
  maxSum = Math.max(maxSum, sum);
}
console.log(maxSum); // 12 (3+4+5)

---

🔁 슬라이딩 윈도우 적용 코드

const solution = (want, number, discount) => {
  const wantMap = {};
  want.forEach((item, i) => wantMap[item] = number[i]);

  const windowMap = {};
  for (let i = 0; i < 10; i++) {
    windowMap[discount[i]] = (windowMap[discount[i]] || 0) + 1;
  }

  let count = 0;
  const isMatch = () => {
    return want.every(item => (windowMap[item] || 0) === wantMap[item]);
  };

  if (isMatch()) count++;

  for (let i = 10; i < discount.length; i++) {
    const removeItem = discount[i - 10];
    windowMap[removeItem]--;
    if (windowMap[removeItem] === 0) delete windowMap[removeItem];

    const addItem = discount[i];
    windowMap[addItem] = (windowMap[addItem] || 0) + 1;

    if (isMatch()) count++;
  }

  return count;
};

---

✅ 장점

항목	설명
✅ 성능 개선	slice() 없이 Map만 수정하므로 전체 연산이 O(n)에 근접
✅ 메모리 절약	매번 새 배열을 만들지 않음
✅ 반복된 연산 제거	동일한 윈도우 상태에서 불필요한 중복 계산 제거

---

❌ 단점

항목	설명
❌ 코드 복잡도 증가	초보자 입장에서는 Map 관리, 원소 제거/추가 등의 로직이 더 복잡해짐
❌ 버그 가능성	상태 관리(count, Map 수정 등) 실수 시 논리 오류가 생기기 쉬움
❌ 특정 문제에 부적합	윈도우 크기가 자주 바뀌거나, 불연속된 영역을 처리할 때는 적합하지 않음

---

📌 결론

• 데이터 양이 크고, 매번 같은 크기의 연속된 범위를 탐색해야 한다면 → 슬라이딩 윈도우 필수
• 다만, 코드의 가독성이 조금 떨어질 수 있으므로 가독성과 성능의 균형을 고려해 선택하면 됨

조건	슬라이딩 윈도우 성능
단순 누적합, 빈도 카운트 등	✅ 빠름 (O(n))
복잡한 상태 유지 (정렬, 중간값 등)	⚠️ 느려질 수 있음
가변 윈도우 크기 문제	❌ 적합하지 않음
윈도우 크기가 배열과 거의 같음	❌ 효과 미미

---