파이썬으로 슬라이딩 윈도우(Sliding Window) 기법 구현하기

파이썬으로 슬라이딩 윈도우(Sliding Window) 기법 구현하기


문제 설명

문자열 `s`와 정수 `k`가 주어졌을 때, 길이가 `k`인 최대 무복 문자 부분 문자열의 길이를 구하는 함수를 작성하세요.


예시 입출력

입력: s = "abcabcbb", k = 3
출력: 3 (최대 무복 문자 부분 문자열은 "abc")

입력: s = "bbbbb", k = 3
출력: 1 (최대 무복 문자 부분 문자열은 "b")

솔루션 코드

def max_length(s, k):
    window = {}
    max_len = 0
    left = 0

    for right in range(len(s)):
        window[s[right]] = window.get(s[right], 0) + 1

        while len(window) > k:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

# 테스트 케이스
print("최대 무복 문자 부분 문자열 길이:", max_length("abcabcbb", 3))
print("최대 무복 문자 부분 문자열 길이:", max_length("bbbbb", 3))

코드 설명

이 포스팅에서는 슬라이딩 윈도우(Sliding Window) 기법을 활용하여 최대 무복 문자 부분 문자열의 길이를 구하는 문제를 해결했습니다. 슬라이딩 윈도우 기법은 배열이나 문자열 등의 연속된 부분 범위를 탐색할 때 유용한 기법으로, 코딩 테스트와 실무에서 다양하게 활용되므로 반드시 학습해야 합니다.

슬라이딩 윈도우 기법은 두 개의 포인터를 사용하여 특정 범위(윈도우)를 유지하면서 이 범위를 슬라이딩하는 방식입니다. 윈도우 내에서 조건을 만족하는지 확인하고, 조건을 만족하지 않으면 윈도우의 크기를 조정합니다.

코드에서는 `max_length` 함수에서 슬라이딩 윈도우 기법을 구현했습니다. `window` 딕셔너리를 사용하여 현재 윈도우 내의 문자와 그 개수를 저장합니다. `left`와 `right` 포인터를 사용하여 윈도우의 범위를 조절합니다.

1. `right` 포인터를 오른쪽으로 이동시키면서 `window`에 문자를 추가합니다.
2. `window`의 크기가 `k`를 초과하면 `left` 포인터를 오른쪽으로 이동시키면서 `window`에서 문자를 제거합니다.
3. `right - left + 1`의 값이 현재까지의 최대 길이보다 크면 업데이트합니다.
4. 1~3 과정을 반복하여 최대 길이를 구합니다.

슬라이딩 윈도우 기법은 다음과 같은 장점이 있어 매우 유용합니다.

1. 시간 복잡도 최적화 : 전체 범위를 탐색하지 않고 윈도우 내에서만 탐색하므로 시간 복잡도를 줄일 수 있습니다.
2. 공간 복잡도 최적화 : 추가적인 자료구조를 사용하지 않고도 문제를 해결할 수 있습니다.
3. 다양한 응용 가능 : 부분 문자열, 부분 배열 등 다양한 유형의 문제에 적용할 수 있습니다.

이러한 장점 때문에 슬라이딩 윈도우 기법은 배열, 문자열, 연결 리스트 등의 선형 자료구조에서 자주 사용됩니다. 또한 코딩 테스트에서도 빈번하게 출제되므로 반드시 숙지해야 할 기법입니다.

슬라이딩 윈도우 기법은 처음에는 어렵게 느껴질 수 있지만, 연습을 통해 익숙해지면 복잡한 문제도 효과적으로 해결할 수 있습니다. 따라서 이 기법을 꾸준히 학습하고 연습하는 것이 중요합니다.