숫자로 이루어진 리스트 nums가 주어졌을 때, 부분 리스트의 최솟값의 2배가 최댓값보다 커야 하는(2 × min > max) 조건을 만족하는 가장 긴 연속 부분 리스트(sublist)의 길이를 구하는 프로그램을 만들어 보겠습니다.
예를 들어 입력이 nums = [10, 2, 6, 6, 4, 4]라면 결과는 4입니다. 부분 리스트 [6, 6, 4, 4]가 이 조건(2 × 4 = 8 > 6)을 만족하는 가장 긴 구간이기 때문입니다.
접근 방법: 슬라이딩 윈도우 + 단조 데크
가능한 모든 부분 리스트를 일일이 검사하면 매우 비효율적입니다. 대신 슬라이딩 윈도우(sliding window) 기법으로 윈도우를 확장·축소해 가면서, 두 개의 단조 데크(monotonic deque)로 현재 윈도우의 최솟값과 최댓값을 빠르게 추적하는 것이 핵심입니다.
ret := 0 (정답을 저장할 변수 초기화)
최솟값 추적용 데크 minq와 최댓값 추적용 데크 maxq를 정의합니다.
윈도우 경계 l := 0, r := 0으로 초기화합니다.
r이 nums의 크기보다 작은 동안 아래 과정을 반복합니다.
n := nums[r]
minq가 비어 있지 않고, n이 minq 마지막 인덱스가 가리키는 값보다 작으면 minq의 마지막 원소를 삭제합니다.
r을 minq의 끝에 삽입합니다.
maxq가 비어 있지 않고, n이 maxq 마지막 인덱스가 가리키는 값보다 크면 maxq의 마지막 원소를 삭제합니다.
r을 maxq의 끝에 삽입합니다.
r := r + 1
l < r이고 nums[minq[0]] * 2 <= nums[maxq[0]]인 동안(조건 위반 시) 아래를 반복합니다.
minq[0]이 l과 같으면 minq의 첫 번째 원소를 삭제합니다.
maxq[0]이 l과 같으면 maxq의 첫 번째 원소를 삭제합니다.
l := l + 1
ret := max(ret, r - l)
ret을 반환합니다.
구현 예제
class Solution:
def solve(self, nums):
from collections import deque
ret = 0
minq, maxq = deque(), deque()
l, r = 0, 0
while r < len(nums):
n = nums[r]
while minq and n < nums[minq[-1]]:
minq.pop()
minq.append(r)
while maxq and n > nums[maxq[-1]]:
maxq.pop()
maxq.append(r)
r += 1
while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
if minq[0] == l:
minq.popleft()
if maxq[0] == l:
maxq.popleft()
l += 1
ret = max(ret, r - l)
return ret
ob = Solution()
nums = [10, 2, 6, 6, 4, 4]
print(ob.solve(nums))
입력
[10, 2, 6, 6, 4, 4]
출력
4
동작 원리 정리
minq의 맨 앞에는 항상 현재 윈도우의 최솟값 인덱스, maxq의 맨 앞에는 항상 최댓값 인덱스가 위치합니다.
새 원소를 추가할 때 뒤쪽에서 단조성을 깨는 인덱스를 제거하므로, 두 데크는 항상 정렬된 상태를 유지합니다.
조건(2 × 최솟값 ≤ 최댓값)이 깨지면 왼쪽 경계 l을 한 칸씩 옮겨 윈도우를 축소하고, 유효한 구간의 길이(r - l)를 계속 갱신합니다.
복잡도 분석
시간 복잡도는 O(n)입니다. 각 인덱스는 각 데크에 최대 한 번 삽입되고 한 번 삭제되기 때문입니다. 공간 복잡도 역시 O(n)입니다.