문제 소개
리스트 nums와 정수 k가 주어졌을 때, 크기가 k인 모든 연속된 하위 리스트(부분 배열)에서 최댓값을 차례대로 구하는 프로그램을 만들어야 합니다. 이 유형은 흔히 슬라이딩 윈도우 최댓값(Sliding Window Maximum) 문제라고 불립니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
nums = [12, 7, 3, 9, 10, 9], k = 3
크기가 3인 하위 리스트는 [12, 7, 3], [7, 3, 9], [3, 9, 10], [9, 10, 9]로 총 네 개이며, 각각의 최댓값은 12, 9, 10, 10입니다. 따라서 기대되는 출력은 다음과 같습니다.
[12, 9, 10, 10]
해결 전략
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- k가 nums의 길이보다 크면 만들 수 있는 윈도우가 없으므로 빈 리스트를 반환합니다.
- 결과를 담을 새로운 리스트 res를 준비합니다.
- 현재 윈도우의 최댓값을 저장할 변수 temp는 nums[0]으로, 해당 값의 인덱스를 가리키는 point는 0으로 초기화합니다.
- 첫 번째 윈도우(인덱스 0 ~ k-1)를 순회하며 최댓값과 그 위치를 갱신한 뒤, temp를 res에 추가합니다.
- 인덱스 k부터 리스트 끝까지 순회하며 아래 규칙에 따라 처리합니다.
- 새 요소 nums[i]가 현재 최댓값보다 작고, 기존 최댓값의 위치(point)가 여전히 현재 윈도우 안에 있다면((i - point) < k) 최댓값은 그대로 유지됩니다.
- nums[i]가 현재 최댓값보다 작지만 기존 최댓값이 윈도우에서 밀려났다면((i - point) >= k), 새 윈도우 범위를 처음부터 다시 훑으며 최댓값과 위치를 재계산합니다.
- 그 외의 경우, 즉 nums[i]가 현재 최댓값 이상이라면 temp와 point를 각각 nums[i]와 i로 갱신합니다.
- 매 반복마다 temp를 res 끝에 추가하고, 모든 순회가 끝나면 res를 반환합니다.
구현 예제
class Solution:
def solve(self, nums, k):
if k > len(nums):
return []
res = []
temp = nums[0]
point = 0
for i in range(k):
if nums[i] > temp:
temp = nums[i]
point = i
res.append(temp)
for i in range(k, len(nums)):
if nums[i] < temp and (i - point) < k:
temp = nums[point]
elif nums[i] < temp and (i - point) >= k:
point = i - k + 1
for j in range(i - k + 1, i + 1):
if nums[j] > nums[point]:
point = j
temp = nums[point]
else:
temp = nums[i]
point = i
res.append(temp)
return res
ob = Solution()
nums = [12, 7, 3, 9, 10, 9]
k = 3
print(ob.solve(nums, k))입력
[12, 7, 3, 9, 10, 9], 3
출력
[12, 9, 10, 10]
시간 복잡도
각 요소를 한 번씩 순회하므로 일반적인 경우 O(n)에 가깝게 동작하지만, 최댓값이 윈도우에서 자주 밀려나 매번 윈도우 전체를 다시 탐색해야 하는 최악의 경우에는 O(n × k)가 될 수 있습니다. 더 엄격한 O(n) 성능이 필요하다면 데크(deque)를 활용한 슬라이딩 윈도우 최댓값 알고리즘을 대안으로 고려해 볼 수 있습니다.