슬라이딩 윈도우 (Sliding Window)

슬라이딩 윈도( Sliding Window) 알고리즘은

배열 또는 리스트의 부분 범위 내의 값에 대한 비교를 수행할 때 좋은 알고리즘이다.

 

슬라이딩 윈도우를 사용한 문제

Longest Substring Without Repeating Characters - LeetCode

 

위 문제를 슬라이딩 코드 없이 풀었을 때는 다음과 같은 코드를 사용했고,

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if s == "" : return 0
        
        for i in range(len(s), 0, -1):
            
            for j in range(len(s) - i + 1):
                
                letterArr = list(s[j : j + i])
                
                if len(set(letterArr)) == len(letterArr):
                    return i

아주 긴 단어에 대해서 테스트를 할때 시간 초과하는 문제가 있다.

 

슬라이딩 윈도우 (Sliding Window)의 가장 기본적인 개념은 중복되는 요소를 재사용하는 것이다

 

leetcode의 문제에 따라 문자열 내에 가장 긴 부분 문자열을 찾아낸다고 할 때 코드는 다음과 같이 작성할 수 있다.

 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # [1]
        maxLength = 0
        leftCursor = 0
        used = {}
        
        # [2]
        for rightCursor, char in enumerate(s):
        	# [4]
            if char in used and leftCursor <= used[char]:
                leftCursor = used[char] + 1
            
            # [3]
            else :
                maxLength = max(maxLength, rightCursor - leftCursor + 1)
                
            used[char] = rightCursor
            
    return maxLength

[1]

우선, 결과에 해당하는 maxLength와 시작 커서, 사용된 문자들( used )를 초기화해준다.

 

[2]

주어진 문자열 s에 대해 enumerate를 사용해 문자와 문자의 인덱스를 함께 넘겨준다

 

[3]

처음 나오는 문자의 경우,

그 문자부터 첫 문자까지의 길이를 maxlength의 값과 비교해 큰 값을 maxlength에 할당하고

커서를 그다음 문자로 옮긴다.

 

[4]

반복되는 문자가 나왔을 때

leftCursor를 이전에 나왔던 문자에서 한 칸 앞으로 이동시킨다.

예) 현재 abcd에서 a가 새롭게 들어왔을 때 기존에 있던 글자는 a이고 leftCursor에 기존 a 글자 인덱스 + 1을 할당해 준다.