[Python] Sliding Window(슬라이딩 윈도우)

■

 

슬라이딩 윈도우는 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘이다. 정렬된 배열에 사용하는 투 포인터와 달리 정렬 여부와 상관 없이 사용된다.

 

크게 어렵지 않은 알고리즘이기때문에 바로 예제를 통해서 이해해보도록 하겠다.

 

 

 

■■

 

다음 예제는 leetcode에서 가져왔다.

 

입력 : arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

출력 : [3, 3, 5, 5, 6, 7]

k 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하면서 최댓값들을 구하는 문제이다.

 

진행 순서는 다음과 같다.

 

 

 

■■■

 

그럼 바로 코드 작성을 해보자

import sys
from collections import deque

def slidingwindow(arr:list, k:int):
    result = []
    window = deque()
    max_ = -sys.maxsize #또는 float('-inf')
    
    for index, value in enumerate(arr):
        window.append(value)
        
        #window의 길이가 k가 될때까지 추가
        if index < k - 1:
            continue
        
        if max_ == -sys.maxsize: #맨 처음 윈도우의 최댓값 = max_
            max_ = max(window)
            
        #현재 숫자가 이전 윈도우의 최댓값보다 크면 현재 윈도우의 최댓값은 현재 숫자가 된다
        elif value > max_:
            max_ = value
            
        result.append(max_) #현재 윈도우 최댓값 추가
        
        #최댓값이 빠지면 다시 초기값으로 설정
        if max_ == window.popleft(): #popleft를 사용하여 시간복잡도 O(1)
            max_ = -sys.maxsize
            
    return result

간단한 예제를 통해서 슬라이딩 윈도우는 이런 것이다라는 것을 이해해보았다.

이후 다양한 문제풀이를 통해 활용해보길 권장한다.