슬라이딩 윈도우

배열이나 문자열에서 일정 범위(윈도우)를 유지한 채 양 끝을 같은 방향으로 이동시키며, 매번 윈도우를 처음부터 다시 계산하지 않고 이전 결과를 재사용해 갱신하는 기법입니다.

동작 과정

고정 크기 윈도우: 길이 3인 부분배열의 최대 합

A = [2, 1, 5, 1, 3, 2]   k = 3

[2,1,5] 1 3 2   sum=8            → max=8
2 [1,5,1] 3 2   sum=8-2+1=7
2 1 [5,1,3] 2   sum=7-1+3=9      → max=9
2 1 5 [1,3,2]   sum=9-5+2=6

답 = 9

가변 크기 윈도우: 중복 없는 최장 부분 문자열

s = "abcabcbb"

right=0 'a' → window=[a]           길이1 → max=1
right=1 'b' → window=[a,b]         길이2 → max=2
right=2 'c' → window=[a,b,c]       길이3 → max=3
right=3 'a' → 중복! left를 이전 'a' 다음으로 이동
            → window=[b,c,a] (left=1) 길이3 → max=3
right=4 'b' → 중복! left를 이전 'b' 다음으로 이동
            → window=[c,a,b] (left=2) 길이3

답 = 3

두 예시 모두 left, right 두 경계가 항상 같은 방향으로만 전진하고 되돌아가지 않습니다. 양 끝에서 좁혀 들어가는 투 포인터와 달리, 슬라이딩 윈도우는 구간(창) 자체를 유지한 채 미끄러뜨린다는 점이 다릅니다.

구현

// 고정 크기 윈도우: 길이 k인 부분배열의 최대 합
int maxSumFixedWindow(int[] a, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += a[i];
    }

    int max = sum;
    for (int right = k; right < a.length; right++) {
        sum += a[right] - a[right - k];
        max = Math.max(max, sum);
    }
    return max;
}

// 가변 크기 윈도우: 중복 없는 최장 부분 문자열
int longestUniqueSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, max = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }
        lastSeen.put(c, right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

복잡도

구분복잡도근거
시간O(N)right가 한 번씩 전진하고, left도 전체 구간에서 합쳐 최대 N번만 전진
공간O(1) ~ O(K)고정 윈도우는 합만 유지하면 O(1), 중복 판별에 HashMap을 쓰면 윈도우 안 원소 수만큼 O(K)

매 윈도우를 처음부터 다시 합산하거나 스캔하면 O(N·K)가 되는데, 이전 윈도우의 결과에서 빠지는 원소만 빼고 들어오는 원소만 더해 갱신하므로 O(N)으로 줄어듭니다.

주의사항

핵심 정리

CSLOG에서 보기