슬라이딩 윈도우

 슬라이딩 윈도우(Sliding Window)란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 슬라이딩 윈도우는 투포인터와 함께 알고리즘 문제 풀이에 매우 유용하게 사용되는 중요한 기법이다.

https://leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

 

 1. 브루트 포스로 계산

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums:
            return nums
        
        r=[]
        for i in range(len(nums) - k + 1):
            r.append(max(nums[i:i+k]))
            
        return r

 매번 윈도우의 최댓값을 계산하기 때문에 이 경우 시간 복잡도는 O(n)이다.

 

 2. 큐를 이용한 최적화

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        results=[]
        window=collections.deque()
        current_max=float('-inf')
        
        for i,v in enumerate(nums):
            window.append(v)
            if i<k-1:
                continue
                
            # 새로 추가된 값이 기존 최댓값보다 큰 경우 교체
            if current_max==float('-inf'):
                current_max=max(window)
            elif v>current_max:
                current_max=v
                
            results.append(current_max)
            
            # 최대값이 윈도우에서 빠지면 초기화
            if current_max==window.popleft():
                current_max=float('-inf')
                
        return results

 필요할 때만 전체의 최댓값을 계산하고 이외에는 새로 추가되는 값이 최대인지만을 확인하는 형태로 계산량을 획기적으로 줄였다. 첫번째 풀이보다 약 5배 정도 빠르다.