문제 개요
숫자로 이루어진 리스트 nums와 정수 k가 주어진다고 가정해 봅시다. 여기서 '연산'이란 리스트 안의 임의의 한 요소를 1만큼 증가시키는 것을 의미합니다. 이 연산을 최대 k번까지 수행할 수 있을 때, 모든 요소가 동일한 값을 갖는 가장 긴 부분 리스트(연속된 구간)의 길이를 구하는 것이 목표입니다.
예시
입력이 다음과 같다고 해보겠습니다.
nums = [3, 5, 9, 6, 10, 7], k = 6
이 경우 출력은 3입니다. 그 이유는 9를 한 번, 6을 네 번 증가시켜 총 5번의 연산(k=6 이내)으로 [10, 10, 10]이라는 길이 3의 동일 요소 구간을 만들 수 있기 때문입니다.
접근 방법: 슬라이딩 윈도우 + 단조 데크(Monotonic Deque)
이 문제는 투 포인터 기반의 슬라이딩 윈도우와 최댓값을 효율적으로 추적하는 단조 감소 데크를 조합하면 O(n) 시간 복잡도로 해결할 수 있습니다. 핵심 아이디어는 현재 윈도우 내의 모든 요소를 윈도우의 최댓값에 맞추는 데 필요한 총 증가량(inc)을 관리하면서, 증가량이 k를 초과하면 윈도우의 왼쪽 끝을 줄여나가는 것입니다.
알고리즘 단계
- nums가 비어 있다면 0을 반환합니다.
- nums와 같은 크기의 데크
wMax를 생성하고, 첫 번째 쌍(nums[0], 0)을 삽입합니다. - 왼쪽 포인터
i = 0, 누적 증가량inc = 0으로 초기화합니다. j를 1부터 nums의 끝까지 반복합니다:- wMax가 비어 있지 않고
wMax[0][1] < i인 동안, 윈도우를 벗어난 왼쪽 요소를 제거합니다. - 현재 최댓값을
pMax = wMax[0][0]으로 저장합니다. - wMax가 비어 있지 않고 마지막 항목의 값이
nums[j]이하인 동안 오른쪽 요소를 제거한 뒤,(nums[j], j)를 삽입합니다. pMax < wMax[0][0]이면inc += (j - i) * (wMax[0][0] - pMax)로 갱신하고, 그렇지 않으면inc += pMax - nums[j]를 더합니다.inc > k라면 윈도우를 축소합니다:inc -= wMax[0][0] - nums[i]를 수행하고, 범위를 벗어난 인덱스를 데크에서 제거한 후 필요한 만큼 증가량을 차감하고i += 1합니다.
- wMax가 비어 있지 않고
- 마지막으로
len(nums) - i를 반환합니다.
구현 예제
from collections import deque
class Solution:
def solve(self, nums, k):
if not nums:
return 0
wMax = deque([(nums[0], 0)], maxlen=len(nums))
i = 0
inc = 0
for j in range(1, len(nums)):
while wMax and wMax[0][1] < i:
wMax.popleft()
pMax = wMax[0][0]
while wMax and wMax[-1][0] <= nums[j]:
wMax.pop()
wMax.append((nums[j], j))
if pMax < wMax[0][0]:
inc += (j - i) * (wMax[0][0] - pMax)
else:
inc += pMax - nums[j]
if inc > k:
inc -= wMax[0][0] - nums[i]
while wMax and wMax[0][1] <= i:
wMax.popleft()
if wMax[0][0] < nums[i]:
inc -= (nums[i] - wMax[0][0]) * (j - i)
i += 1
return len(nums) - i
ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))
입력
[3, 5, 9, 6, 10, 7], 6
출력
3
정리
이 알고리즘은 각 요소가 데크에 최대 한 번 들어가고 한 번 나오므로 전체 시간 복잡도는 O(n)입니다. 슬라이딩 윈도우와 단조 데크를 함께 사용하면 '최대 k번의 증가 연산으로 균등하게 만들 수 있는 가장 긴 구간' 유형의 문제를 선형 시간에 효율적으로 해결할 수 있습니다.