75. Sliding Window Maximum

🎯 leetcode - 239. Sliding Window Maximum

📌 문제

- 파이썬 알고리즘 인터뷰 75번 문제

📌 날짜

2020.03.05

📌 시도 횟수

8 try / Failed

💡 Code

from collections import deque


class Solution:
    def maxSlidingWindow(self, nums, k):
        result = []
        bigger = deque()
        for i, n in enumerate(nums):
            # 항상 가장 왼쪽 값이 현재 window의 최댓값이 되도록 설정
            while bigger and nums[bigger[-1]] <= n:
                bigger.pop()

            # 매 반복문마다 슬라이딩 윈도우가 한개씩 늘어남(index값을 저장)
            bigger += [i]

            # 슬라이딩 윈도우 크기가 k보다 커지지 않도록 함
            if i - bigger[0] >= k:
                bigger.popleft()

            # 슬라이딩 윈도우의 요소가 k개보다 작으면 (아직 윈도우가 다 만들어진 상태가 아니므로) 
            # result에 값을 추가하지 않는다. 예를 들어서, k = 3일 때.. 초기 반복문 2회는 아직 
            # 슬라이딩 윈도우의 사이즈가 제대로 만들어지지 않았기 때문에 패스한다.
            if i < k - 1:
                continue
            result.append(nums[bigger[0]])

        return result

💡 문제 해결 방법

*슬라이딩 윈도우가 저장하는 요소가 '값'이 아닌 '인덱스'가 되도록 했다!
> 아무래도 '값'으로 저장하게 되면 나중에 슬라이딩 윈도우의 크기를 구하는 과정에서
계속해서 'len()' 연산을 사용해야 되므로 속도가 느려질 것을 미리 방지하고자 한 것 같다.

1. 항상 현재 슬라이딩 윈도우의 가장 '왼쪽 값이 max가 되도록' 했다.
> 신기하게 최댓값을 구할 때 max를 사용하지 않고 while문으로 pop했다.

2. 매 반복문이 돌 때마다 슬라이딩 윈도우의 크기가 1개씩 늘어난다.
> 그렇다면 1개씩 빼주기도 해야겠지? 
> 하지만 1번에서 맘대로 최댓값이 가장 왼쪽에 오도록 pop 해버려서...
매 반복문마다 뺄 수는 없어졌다. 과연 어떻게 슬라이딩 윈도우의 크기를 조절할 수 있을까?

3. 슬라이딩 윈도우의 크기는 k보다 커질 수 없다! <윈도우 크기 조절>
> bigger[0]가 현재 슬라이딩 윈도우의 크기에 대한 정보를 가지고 있다!
> i - bigger[0] >= k 가 되는 경우에만 popleft()를 해주면 된다.

4. result에 현재 최댓값 더해주기
> 현재 최댓값은 가장 왼쪽 인덱스의 값이므로 nums[bigger[0]]을 더해주면된다.
> 단, 슬라이딩 윈도우가 아직 k 크기만큼 형성되지 않은 초기의 케이스는 제외시켜야된다!

💡 새롭게 알게 된 점

- 슬라이딩 윈도우에 대해 알게 되었다!
- 값 대신 index를 저장할 때의 장점을 느껴볼 수 있었다.
값은 좀 더 직관적이지만, 매번 리스트의 크기를 구해야 하는 상황이 반복된다면
차라리 값 대신 인덱스를 사용하는 것도 좋은 방법인 것 같다!

❌ (한번에 맞추지 못한 경우) 오답의 원인

1. 첫번째 시도

처음에는 브루트 포스로 매번 현재 슬라이딩 윈도우의 max를 구해서 푸는 법을 생각했다.
그런데 역시 브루트 포스 방법으로는 시간 초과가 떴다. 아래는 그 코드이다.

# 첫번째 시도 : 브루트 포스로 풀기
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        for idx in range(len(nums) - k + 1):
            max_num = max(nums[idx : idx + k])
            result.append(max_num)
        return result

2. 두번째 시도

브루트 포스에서는 모든 경우에 대하여 max를 구했지만, 두번째 시도에서는 꼭 최댓값을 갱신해줄 필요가 없는 경우에는 max 연산을 수행하지 않도록 해주었다.
만약 새롭게 슬라이딩 윈도우에 추가된 값이 기존의 최댓값보다 크다면, 최댓값을 갱신해주었고 아니라면 그대로 놔두었다.
단, 기존의 최댓값이 현재 슬라이딩 윈도우 범위에서 빠지는 경우, 무조건 다음 차례에서는 최댓값을 다시 새롭게 구해줄 수 있도록 current_max = float('-int')로 표시해두었다.
그런데 이 방법도 시간 초과가 떴다! 😒😒😒
그래서 아무래도 이 max()로 인해 계속 문제가 생기는 것 같다고 생각하게 되었다.

# 두번째 시도 : max를 꼭 필요할 때만 사용하기
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        window = 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

            result.append(current_max)

            if current_max == window.popleft():
                current_max = float("-inf")

        return result