239. Sliding Window Maximum

Sliding Window Maximum - LeetCode

슬라이딩 윈도 사이즈 k가 주어진다.

슬라이딩 윈도를 수행하면서 윈도 내 가장 큰 정수를 list로 저장해서 반환하는 문제다.

 

예시는 다음과 같다.

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

접근법을 생각해보자.

 

우선 Brute-Force, 당연히 TLE가 나는 문제다. 슬라이딩 윈도 내부를 매번 탐색해서 최댓값을 찾으라는 문제가 아니다.

뭔가 더 빠르고 효율적인 방법을 사용해야 한다.

 

대충 생각하면 이런 자료구조나 방법이 있으면 해결할 수 있다.

1. 이 자료구조에 어떤 값을 넣으면 그 값이 자동으로 정렬된다. 그래서 최댓값, 최솟값을 바로 알 수 있다.
2. 이 자료구조에 어떤 값을 제외하면 기존 정렬이 유지된 상태로 최댓값 최솟값을 바로 알 수 있다.
3. 이 자료구조에 어떤 key를 넣고 그 key에 해당하는 value를 같이 저장할 수 있다면 슬라이딩 윈도 내부에 중복되는 값도 한꺼번에 처리할 수 있을 것 같다.

이런 자료구조로는 Java의 TreeMap이 있다.

TreeMap (Java Platform SE 8 )

TreeMap을 쓰면 한 방에 위 조건을 만족하면서 원하는 최댓값을 선형 시간 복잡도로 얻어낼 수 있다.

이중 우선순위 큐 같은 문제에서도 TreeMap을 사용하면 한 번에 해결할 수 있다.

 

하지만 이런 특수한 자료구조를 사용해서 풀라고 낸 문제는 아닌 것 같고...

 

1. Deque를 사용한 풀이

from typing import *
from collections import deque


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

        if k == 1:
            return nums

        answer = []
        q = deque([])
        for i, val in enumerate(nums):
            while q and q[0] <= i - k:
                q.popleft()

            while q and nums[q[-1]] <= val:
                q.pop()

            q.append(i)

            if i >= k - 1:
                answer.append(nums[q[0]])

        return answer

시간이 어마무시하지만 정상이다

Deque를 사용하면 O(N)은 아니더라도 상수 시간대로 문제를 해결할 수 있다.

그림과 함께하는 설명은 링크를 참고할 것.

 

Deque에는 index를 값이 아닌 인덱스를 저장하면서 진행한다.

1. (첫 번째 while문) 우선 deque에 범위에 맞지 않는 index를 전부 popleft()한다.
2. (두 번째 while문) 그 뒤 현재 index의 값보다 작은 값을 가리키는 deque의 index를 전부 pop()한다. 이것 때문에 현재 윈도의 최댓값을 유지할 수 있다.
3. 현재 index를 append()한다.

결국 이것을 반복하면 deque 안의 index가 가리키는 값은 단조 증가, 혹은 단조 감소를 띄는 monotone queue 형태를 가지게 된다.

이 로직이 이해가 안 되어서 굉장히 오랫동안 붙잡고 있었는데 슬라이딩 윈도 기초 응용 정도 되는 문제인 것 같다... 

참고로 DP로도 풀 수 있고 구간 트리도 사용해서 해결 가능하다고 한다.

 

갈길이 멀다...