파이썬으로 '2×최솟값 > 최댓값' 조건을 만족하는 가장 긴 연속 부분 리스트 찾기

숫자로 이루어진 리스트 nums가 주어졌을 때, 2 × (부분 리스트의 최솟값) > (부분 리스트의 최댓값) 조건을 만족하는 가장 긴 연속 부분 리스트(sublist)의 길이를 구하는 문제입니다.

예를 들어 입력이 nums = [10, 2, 6, 6, 4, 4]라면 출력은 4가 됩니다. 그 이유는 부분 리스트 [6, 6, 4, 4]에서 최솟값은 4, 최댓값은 6이고, 2 × 4 = 8 > 6이므로 조건을 충족하며, 이보다 긴 구간 중 조건을 만족하는 것은 없기 때문입니다.

접근 방법: 슬라이딩 윈도우 + 모노토닉 데크

이 문제는 투 포인터(슬라이딩 윈도우) 기법과 두 개의 모노토닉 데크(double-ended queue)를 활용하면 O(n) 시간에 해결할 수 있습니다.

minq: 현재 윈도우의 최솟값 인덱스를 오름차순으로 유지하는 데크
maxq: 현재 윈도우의 최댓값 인덱스를 내림차순으로 유지하는 데크

오른쪽 포인터 r로 요소를 하나씩 추가하고, 조건 minq[0] * 2 > maxq[0]이 깨질 때마다 왼쪽 포인터 l을 이동시켜 윈도우를 축소합니다. 각 시점에서 윈도우 크기 r - l의 최댓값이 곧 정답이 됩니다.

알고리즘 단계

결과값 ret을 0으로 초기화합니다.
최솟값용 데크 minq와 최댓값용 데크 maxq를 빈 상태로 생성합니다.
왼쪽 포인터 l = 0, 오른쪽 포인터 r = 0으로 초기화합니다.
r이 리스트 끝에 도달할 때까지 다음을 반복합니다:
- 현재 값 n = nums[r]을 가져옵니다.
- minq가 비어 있지 않고 n이 minq 마지막 인덱스의 값보다 작으면 뒤에서 요소를 제거한 후 r을 추가합니다. (최솟값 유지)
- maxq가 비어 있지 않고 n이 maxq 마지막 인덱스의 값보다 크면 뒤에서 요소를 제거한 후 r을 추가합니다. (최댓값 유지)
- r을 1 증가시킵니다.
- l < r이면서 nums[minq[0]] * 2 <= nums[maxq[0]]인 동안:
  - minq[0]이 l과 같으면 minq 앞에서 요소를 제거합니다.
  - maxq[0]이 l과 같으면 maxq 앞에서 요소를 제거합니다.
  - l을 1 증가시킵니다.
- ret을 ret과 (r - l) 중 더 큰 값으로 갱신합니다.
반복이 끝나면 ret을 반환합니다.

구현 예제

다음 파이썬 코드로 위 알고리즘을 확인해 보겠습니다.

from collections import deque

def solve(nums):
    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

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

입력

[10, 2, 6, 6, 4, 4]

출력

시간 복잡도 분석

각 인덱스는 두 데크에 최대 한 번씩만 추가되고 제거되므로, 전체 반복문은 리스트 길이 n에 대해 선형적으로 동작합니다. 따라서 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 단순히 모든 부분 리스트를 확인하는 O(n²) 이상의 방법보다 훨씬 효율적입니다.