문제
문제 : https://leetcode.com/problems/sliding-window-maximum/
주어진 정수 숫자 배열과 왼쪽에서 오른쪽으로 이동하는 k 크기의 슬라이딩 윈도우가 있다고 하자. 슬라이딩 윈도우 내에는 k 개의 숫자만 존재한다. 슬라이딩 윈도우가 한 칸씩 오른쪽으로 이동할 때마다의 최댓값을 반환하라
예시 )
Input: nums = [1,3,-1,-3,5,3,6,7], 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
풀이
슬라이딩 윈도우 문제로, 슬라이딩 윈도우의 맨 첫 번째 원소를 최댓값으로 유지하는 방식으로 문제를 풀어낼 수 있다.
1. 변수 초기화
결과 리스트를 저장할 result와 슬라이딩 윈도우를 저장한 window를 선언한다. window는 양끝에서 원소를 추가하거나 삭제할 때 사용하는 deque를 사용했다.
result = []
window = deque()
2. 슬라이딩 윈도우에 원소 추가
값을 추가할 때는 윈도우 내의 최신값과 현재 숫자를 비교하여 윈도우 내에 현재 원소보다 더 작은 원소가 없도록 한다.
for i, num in enumerate(nums):
# 정렬
while window and window[-1] < num:
window.pop()
window.append(num)
예로 들어 리스트가 아래와 같다고 가정하자.
[1, 3, -1, -3, 5, 3, 6, 7]
그리고 슬라이딩 윈도우에 [1]만 저장되어 있고 현재 값이 3이라면, 슬라이딩 윈도우에서 1은 제거하고 3만 저장한다.
이런 방식으로 슬라이딩 윈도우의 첫 번째 원소는 항상 최댓값을 유지하도록 한다.
3. 슬라이딩 윈도우 밖 숫자 제거
만약 숫자가 계속 내림차순으로 진행되어 슬라이딩 윈도우의 길이가 정해진 길이를 초과할 때는, 슬라이딩 윈도우에 가장 먼저 추가된 원소를 제거하여 길이를 유지한다.
if i >= k and nums[i - k] == window[0]:
window.popleft()
4. 슬라이딩 윈도우 내 최댓값을 결과 리스트에 저장
인덱스가 정해진 길이(K) 이상이 되면 슬라이딩 윈도우의 최댓값을 결과 리스트에 저장한다.
if i >= k - 1:
result.append(window[0])결과적으로 result 를 반환하면 된다.
전체 코드는 접은글로 작성한다.
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
window = deque()
for i, num in enumerate(nums):
# 정렬
while window and window[-1] < num:
window.pop()
window.append(num)
# 윈도우 바깥 원소 처리
if i >= k and nums[i - k] == window[0]:
window.popleft()
if i >= k - 1:
result.append(window[0])
return result
실행 결과
nums가 [1,3,-1,-3,5,3,6,7]이고 k가 3일 때 슬라이딩 윈도우의 내용을 출력하면 다음과 같다.
슬라이딩 윈도우의 첫 번째 원소가 윈도우 내 최댓값으로 유지되는 모습을 확인할 수 있다.
참고 문서