문제
https://leetcode.com/problems/sliding-window-maximum/
문제풀이
que 자료구조에는 윈도우 내에서 최대값이 될 후보 인덱스만 저장하는 변수이다. 해당 변수에서는 윈도우 범위가 바뀜에 따라 탈락하는 변수를 제거하는 작업을 하고 추가된 값(add_val)보다 작은 값은 제거하는 작업을 수행한다. 여기서 중요한 부분은 추가된 값 이후에 존재하는 값들은 추가된 값보다 작더라도 추후에 add_val이 탈락할 가능성이 있으므로 que에 보관되어 관리되어야 한다는 점이다. 이 부분이 핵심이다.
l, p, r, n은 각각 윈도우의 왼쪽 끝, 현재 후보 인덱스, 윈도우의 오른쪽 끝, 배열의 길이를 나타낸다.
que의 목적은 현재 윈도우 내에서 가장 큰 값의 인덱스를 저장하고 윈도우가 이동함에 따라 필요없는 인덱스를 제거한다.
주요 루프 설명
초기에 que에는 첫 번째 원소의 인덱스 0이 추가한다.
r은 윈도우의 오른쪽 끝을 가리키며, 윈도우를 오른쪽으로 이동시킨다.
현재 윈도우에 새로 들어온 숫자를 add_val에 저장한다.
while que and que[0] < l: 루프는 윈도우를 오른쪽으로 이동함에 따라 벗어난 인덱스들을 데크에서 제거한다. 이는 que의 첫 번째 인덱스가 현재 윈도우 왼쪽 끝보다 작아질 때까지 반복한다.
while que and add_val > nums[que[-1]]: 루프는 새로운 add_val보다 작은 값을 가진 인덱스들을 데크에서 제거한다. 이는 현재 윈도우 내에서 add_val보다 작은 값들은 최대값이 될 가능성이 없기 때문이다.
que.append(r)를 통해 현재 r 인덱스를 데크에 추가한다.
위 코드는 주어진 배열에서 크기 k의 슬라이딩 윈도우를 오른쪽으로 이동시키면서 각 윈도우에서의 최대값을 효율적으로 찾아내는 알고리즘을 구현한 것이다. 이 알고리즘의 시간 복잡도는 O(n)으로, 각 인덱스를 데크에 한 번씩만 추가하거나 제거하므로 선형 시간에 문제를 해결할 수 있다.
코드
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = deque()
ans=[]
l,p,r,n=0,0,1,len(nums)
if k<=1:
return nums
if n==k:
return [max(nums)]
que.append(0)
while r<n:
add_val=nums[r]
#print("before",que,l,r,add_val)
while que and que[0] < l:
que.popleft()
while que and add_val>nums[que[-1]]:
que.pop()
que.append(r)
#print("after",que,l,r,add_val)
if r-l==k-1:
l+=1
#print("add ans",nums[que[0]])
ans.append(nums[que[0]])
r+=1
return ans
Lookback
- 처음 문제를 접할때는 윈도우 범위 내 첫번째,두번째 값을 관리하면 쉽게 해결이 될 것이라고 생각하였다. 하지만 윈도우가 계속 이동함에 따라서 이후 세번쨰 값,네번째 값 등 후순위 값들도 필요하다는 점을 깨닫고(=정확히는 최대값이 윈도우 범위 중 가장 첫번쨰에 위치하여 이동할때마다 탈락하는 그러한 케이스에서 발생한다.) 큐를 활용하여 해결하였다.
