"75. 최대 슬라이딩 윈도우" 문제 시간초과에 대해

[sohyunwriter]

교재의 "75. 최대 슬라이딩 윈도우" 문제 관련 이슈 남깁니다.

1) (571~574쪽) "75. 최대 슬라이딩 윈도우" 문제 풀이 부분

교재의 풀이 1, 풀이 2 모두 time out error 가 납니다.

각 window 마다 max를 매번 계산하는 부분 때문으로 보입니다.
test case의 nums 리스트가 100,000개, k가 50,000개일 경우,
교재의 풀이방식은 100,000*50,000 이므로 50억으로 시간초과가 납니다.

그래서 deque를 이용해서 O(n)으로 풀었더니 1492 ms로 전체 풀케이스를 통과할 수 있었습니다.

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

sol = Solution()
print(sol.maxSlidingWindow(nums=[1,3,-1,-3,5,3,6,7], k=3))

2) (572쪽) 시간복잡도 서술 부분

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

K의 크기에 영향을 받으므로, O(N*K)가 더 정확할 것 같습니다.

[likejazz]

안녕하세요. 리트코드의 테스트케이스가 변경되어 풀이에 많이 고생하셨을거 같네요.
이 문제의 경우 책 출간 이후 테스트케이스가 추가되어 문제 난이도가 상승한 경우 입니다.
(이슈 #66 참고)

비슷한 예로 Two Sum 문제의 경우 오히려 테스트케이스가 삭제되어 문제 난이도가 낮아지면서 변별력이 사라진 바 있습니다.
(이슈 #62 참고)

이미 책이 출간된 상태에서 매 번 사이트의 변경을 따라가면서 반영할 수 없으므로, 깃헙의 코드 풀이에만 별도로 해당 사항을 표기하도록 하겠습니다. 추후 개정판이 나오게 되면 알려주신 새로운 풀이를 반영하겠습니다.

그리고, 시간 복잡도는 이 책에서는 대부분 상수항을 생략하기는 했지만 보다 명확해 보이므로, 이번에는 k를 추가하여 O(k * n)으로 수정하도록 하겠습니다. 감사합니다.

[sohyunwriter]

네 감사합니다! 깔끔하게 잘 정리해주신 책 덕분에 잘 공부하고 있습니다~!!
파이썬 알고리즘 책 중에는 레전드라고 생각해서 주변 친구들에게 많이 추천하고 다니는데 많이 소문내고 다닐게요^^
2판 3판 4판 n판까지 응원합니다.

[dalinaum]

제 풀이도 공유해봅니다. 값을 append로 추가도 해보고 반대로 appendleft로 추가도 해보았는데 전자의 버전이 더 효과적이네요.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()
        results = []

        for i, v in enumerate(nums):
            while dq and nums[dq[-1]] < v:
                dq.pop()

            dq.append(i)

            while dq[0] <= i - k:
                dq.popleft()
            
            if i >= k - 1:
                results.append(nums[dq[0]])

        return results

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = collections.deque()
        results = []

        for i, v in enumerate(nums):
            while dq and nums[dq[0]] < v:
                dq.popleft()

            dq.appendleft(i)

            while dq[-1] <= i - k:
                dq.pop()
            
            if i >= k - 1:
                results.append(nums[dq[-1]])

        return results