Leetcode 239. Sliding Window Maximum - Python

from LeetCode 239

 

Leetcode 239 문제 보기

 

문제 이해하기

정수로 구성된 리스트 nums와 양수 k가 주어진다.

k 사이즈의 리스트가 nums 내에서 움직인다.

이때 각 'k 사이즈 리스트(window)' 내 가장 큰 값을 결과 리스트에 담아, 최종적으로 결과 리스트를 출력하라.

 

아이디어 구상

우선 문제를 보면, Brute Force한 O(n^2)의 알고리즘이 바로 떠오른다.

Slicing를 이용하거나 nums를 한바퀴 순회하며 window를 업데이트하고 매순간 window내 max를 찾는 경우가 되겠다.

별도의 시간복잡도에 관한 constraint가 없었기 때문에 혹시나 하는 마음에 Brute Force 풀이를 submit해봤으나,

TLE(Time Limit Exceeded)가 떴다.

 

그렇다면 이를 좀 더 효율적으로 처리할 수 있는 방법은 무엇일까.

 

조금 더 생각해보면 매순간 window내 max를 찾는 과정을 간소화할 수 있을 것 같다.

왜냐하면 결국 한 snapshot의 window에서의 max 외 나머지 값들은 다음 snapshot의 window에서 또한 고려할 필요가 없기 때문이다. 즉, window내 max값만 어딘가 계속 보관하고 업데이트해주면 된다.

여기서 조심할 것은, window가 이동하면서 기존의 max 중에서 인덱스 범위의 초과로 인해 삭제해줘야 할 것이 발생할 수도 있다는 것이다. 때문에 다음 두 가지를 고려해 코드를 구현하면 되겠다.

 

1. nums를 단방향 순회하며 window내 max를 업데이트

2. 순회 시 window의 index 범위를 초과한 원소들 삭제

 

이를 처리하기 위해 deque 자료구조를 선택했다.

양 옆에서 추가/삭제가 이루어지므로 deque를 사용해 O(1)으로 처리가능하기 때문이다.

 

풀이

가장 먼저 리스트 nums와 window의 사이즈가 동일한 경우, 그냥 nums 내 max값을 리턴하면 된다.

if len(nums) == k:
    return [max(nums)]

 

결과를 담을 리스트 res와 deque인 window를 선언한다.

window = collections.deque()
res = []

 

이후 nums를 순차적으로 순회하며 window의 가장 왼쪽에 있는 값이 바로 max값이 되도록 window를 업데이트한다.

또한 그 최대값이 순회를 하며 index 범위 바깥의 값이 되었다면 미련없이 popleft를 통해 삭제해준다.

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

 

맨 처음 window 업데이트를 시작할 때까지를 제외하고, 이후부터는 res를 업데이트해준다.

if i - k + 1 >= 0:
    res.append(nums[window[0]])

 

전체 코드는 다음과 같다.

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

---

Leetcode 239. Sliding Window Maximum

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

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다