슬라이딩 윈도우 1 - Sliding Window Maximum

shsh·2021년 8월 18일

Python-Algorithm

목록 보기

7/8

슬라이딩 윈도우

: 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

2 개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하는 네트워크 용어이기도

투 포인터와 유사

투 포인터: 주로 정렬된 배열 대상, 윈도우 사이즈 가변, 좌우 포인터가 자유롭게 이동
슬라이딩 윈도우: 정렬 여부에 관계 없이 활용, 윈도우 사이즈 고정, 좌/우 한쪽 방향으로만 이동
혼용되기도 함

239. Sliding Window Maximum

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

My Answer 1: Time Limit Exceeded (58 / 61 test cases passed.)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        i = 1
        j = k+1
        idx = nums.index(max(nums[:k]))
        ans = [max(nums[:k])]
        while j <= len(nums):
            if idx < i:
                m = max(nums[i:j])
                idx = i+nums[i:j].index(m)
            elif ans[-1] < nums[j-1]:
                idx = j-1
            ans.append(nums[idx])
            i += 1
            j += 1
        
        return ans

처음 nums[0:k] 의 최댓값을 ans 에 저장 / idx 는 최댓값의 인덱스

i 와 j 는 k 길이를 유지하면서 오른쪽으로 이동

최댓값이 윈도우를 벗어났을 경우 => if idx < i:
새로운 최댓값 찾기

윈도우 안에 있을 경우는 새로 들어오는 nums[j-1] 와 비교해서 더 큰 값으로 update

Solution 1: Accepted (Runtime: 1664 ms - 90.30% / Memory Usage: 30.2 MB - 56.15%)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque = collections.deque()
        res = []
        for i, num in enumerate(nums):
            while(deque and nums[deque[-1]] < num):
                deque.pop()
            if(deque and i - deque[0] >= k):
                deque.popleft()
            deque.append(i)
            if i+1 >= k:
                res.append(nums[deque[0]])
            
        return res

선입선출(FIFO) => 큐 사용
파이썬에서의 큐 => 주로 데크 사용 collections.deque()

while(deque and nums[deque[-1]] < num):
=> deque 에 있는 값들 중에 현재 숫자보다 작은 애들은 모두 pop

if(deque and i - deque[0] >= k):
=> 윈도우의 범위를 벗어났을 때 맨 앞의 값 pop

처음 k-1 개는 deque 에만 들어가도록 => if i+1 >= k:
window size 만큼 확보됐을 때부터 res 에 넣기 시작