슬라이딩 윈도우(Sliding Window) & 투 포인터(Two Pointer)

1. 슬라이딩 윈도우(Sliding Window) & 투 포인터(Two Pointer)란?

- 모두 배열이나 문자열 같이 순차적으로 저장된 데이터에서 연속된 구간(윈도우)을 효율적으로 탐색하기 위한 기법이다.

- 연속 구간 내 조건데 따라 최대/최소 합, 길이 등을 빠르게 계산할 수 있다.

 

1-1. 유사점 및 차이점

- 유사점: 둘 다 연속된 구간을 탐색하는데 초점을 맞추며, 포인터를 이동시키는 방식으로 중복 계산을 줄인다.

- 차이점: 슬라이딩 윈도우는 고정 크기의 윈도우를 가지며 투 포인터는 2개의 인덱스를 통해 동적 윈도우를 가진다.

 

2. 슬라이딩 윈도우 & 투 포인터 구현

2-1. 고정 길이(슬라이딩 윈도우) 구현

- 정수 배열이 주어졌을 때 길이가 k인 연속 부분 배열의 합들 중 최대값을 구하는 문제

public class SlidingWindowExample {
    public static int slidingWindow(int[] arr, int k) {
        // 초기 윈도우 합 계산
        int windowSum = 0;
        for(int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        // 최대값
        int maxSum = windowSum;

        // 윈도우를 오른쪽으로 한칸씩 이동하면서 업데이트
        for(int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i-k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        // 예제 데이터
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;

        int result = slidingWindow(arr, k);

        // 출력: 7
        System.out.println(result);
    }
}

 

2-2. 가변 길이(투 포인터) 구현 

- 문자열 s에서 서로 다른 문자가 최대 k개인 가장 긴 부분의 문자열 길이를 구하는 문제

public class TwoPointerExample {
    public static int twoPointer(String s, int k) {
        Map<Character, Integer> window = new HashMap<>();
        int windowStart = 0;
        int maxLength = 0;

        // 문자열의 끝 인덱스를 0부터 증가시키며 윈도우 확장
        for(int i = 0; i < s.length(); i++) {
            char rightChar = s.charAt(i);
            window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);

            // 윈도우 내 서로 다른 문자의 수가 k를 초과하면 조건을 만족할 때까지 윈도우 축소
            while(window.size() > k) {
                char leftChar = s.charAt(windowStart);
                window.put(leftChar, window.get(leftChar) - 1);

                if(window.get(leftChar) == 0) {
                    window.remove(leftChar);
                }
                windowStart++;
            }
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        // 예제 데이터
        String s = "eceba";
        int k = 2;

        int result = twoPointer(s, k);

        // 출력: 3
        System.out.println(result);
    }
}