[파이썬 알고리즘 인터뷰][슬라이딩윈도우] 최대 슬라이딩 윈도우

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

k개의 슬라이드마다 최대값을 담아 출력

 

책에서 구현된 코드

# 테스트케이스 변경으로 현재 책의 방식으로 통과되지 않음 (책에도 이슈관련 내용이 적혀있음)
# github에 다른 분이 작성하신 수정된 방식

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deq, ans = deque(), []

        for i in range(len(nums)):
            # 앞에서부터 out of window -> 제거
            if deq and i-deq[0] == k:
                deq.popleft()

            # 뒤에서부터 현재 추가할 숫자보다 작으면 -> 제거 (deq에 불필요한 숫자 없도록!)
            while deq and nums[deq[-1]] <= nums[i]:
                deq.pop()

            deq.append(i) # 현재 숫자 추가( (i, num[i])로 저장해도 되나, 숫자 위치 저장만 해 space 줄임)

            # 출력 부분 (현재 위치 >= window size일 때)
            if i+1 >= k:
                ans.append(nums[deq[0]])  # 맨 앞은 현재 window 에서 가장 큰 수

        return ans

https://github.com/onlybooks/algorithm-interview/issues/67

"75. 최대 슬라이딩 윈도우" 문제 시간초과에 대해 · Issue #67 · onlybooks/algorithm-interview

 

기억해야할 기법

• 순차 삽입되는 값들의 최대값 찾기
  
  • deque의 left/right 사용 -> q[0]가 최대값
  • left가 삽입될 값보다 작을 때까지 pop
    - left만 pop하면 [3, 1, 2]에 0을 삽입할 때 최대값이 아님
  • right가 삽입될 값보다 작을 때까지 pop
    - [3, 1, 2] -> [3, 1]에서 2가 삽입될 때 1을 pop하며 q[0]가 최대값이 되게 만들어줌 

 

내가 구현한 코드

# 위 코드 보고 구현해봄
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        answer = []
        if len(nums) == 1:
            return nums

        q = deque()
        for i in range(len(nums)):
            while q and (q[0] <= i-k or nums[q[0]] < nums[i]):
                q.popleft()
            while q and nums[q[-1]] < nums[i]:
                q.pop()
            q.append(i)
            if k-1 <= i:
                answer.append(nums[q[0]])
        return answer

• deque를 제대로 사용한 첫 예제인 것 같다
• 투포인터로 양쪽에서 최대값을 찾아나아가는 방법과 유사하다