[알고리즘] 슬라이딩 윈도우 풀이 가이드

개념

창문을 한칸 씩 이동해서 문제가 요구하는 조건을 체크하는 것입니다.
가이드 순서는 아래와 같습니다.

1. 윈도우에 담을 기존 원소(데이터)를 확인합니다.
2. 윈도우의 left, right 포인터를 0부터 시작합니다.
   • left는 윈도우의 왼쪽 끝, right는 왼도우의 오른쪽 끝을 나타냅니다.
   • 조건에 따라 시작 지점은 변경합니다.
3. right를 하나씩 증가시키면서 배열을 순회합니다.
   • right가 증가할 때마다 기존 데이터를 기반으로 새로운 원소(데이터)를 반영합니다.
4. 윈도우에 추가된 원소를 문제의 조건에 맞춰 처리합니다.
   • left ~ right를 순회해서 처리합니다.
   • 예 빈도수 계산, 함계 계산, 최댓값/최솟값 업데이트 등
5. 문제의 조건을 벗어나면(right 로직 마지막) 조건을 만족할 때까지 left 포인터를 오른쪽으로 이동시킵니다.
   • 이 과정에서 윈도우에서 원소가 갱신됩니다.
   • 윈도우의 유효셩을 체크합니다.
6. 매번 윈도우를 업데이트할 때마다 결과를 저장하거나 갱신합니다.

---

Java 코드로 확인해보자

윈도우 내의 합 문제

int[] arr = {1, 3, 2, 5, 1, 1, 2, 3};
int targetSum = 8;

// 슬라이딩 윈도우의 두 포인터 left, right 선언
int left = 0, windowSum = 0;

// right를 기준으로 배열 전체를 순회
for (int right = 0; right < arr.length; right++) {

    // right가 가리키는 원소를 윈도우에 포함
    windowSum += arr[right];

    // 윈도우 내 합이 조건(targetSum)을 초과하면, 초과하지 않을 때까지 left를 오른쪽으로 이동
    while (windowSum > targetSum) {
        windowSum -= arr[left]; // left 원소를 윈도우에서 제거
        left++;                 // left 포인터 이동
    }

    // 조건을 만족하면 현재 윈도우 범위를 출력
    if (windowSum == targetSum) {
        System.out.println("조건 만족 윈도우: [" + left + ", " + right + "]");
    }
}

---

코드 흐름을 간단하게 정리하면

right로 원소 추가 → 윈도우 합 증가하고
조건을 만족하지 않으면 left로 원소 제거 → 윈도우 합 감소
조건 만족 시 현재 윈도우 범위 출력

---

슬라이딩 윈도우가 유용한 문제 유형은?

• 연속된 구간의 합 또는 특정 조건을 만족하는 부분 배열 찾기
• 최대 길이 부분 배열, 최소 길이 부분 배열 찾는 문제
• 문자열 또는 배열에서 중복 제거 후 연속 구간 찾기 문제

---

요약

두 포인터로 윈도우 범위를 유지하고 right 순회에서 원소 추가하고, left로 조건을 유지하는 것입니다.