Python 슬라이딩 윈도우로 최댓값·최솟값 차이가 k 이하인 가장 긴 부분 리스트 찾기

문제 소개

숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 구간 안에서 최댓값과 최솟값의 절대 차이가 k 이하가 되는 가장 긴 연속 부분 리스트(sublist)의 길이를 구하는 프로그램을 만들어 보겠습니다.

예시

nums = [2, 4, 6, 10], k = 4가 주어진다면 결과는 3입니다. [2, 4, 6]을 선택하면 최댓값 6과 최솟값 2의 차이가 정확히 4로 조건을 만족하고, 이보다 긴 구간은 조건을 벗어나기 때문입니다.

접근 방법: 슬라이딩 윈도우 + 단조 데크

이 문제는 투 포인터 기반의 슬라이딩 윈도우와 두 개의 단조 데크(double-ended queue)를 함께 사용하면 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• maxd: 현재 윈도우의 최댓값 후보를 내림차순으로 유지하는 데크 (맨 앞이 항상 윈도우의 최댓값)
• mind: 현재 윈도우의 최솟값 후보를 오름차순으로 유지하는 데크 (맨 앞이 항상 윈도우의 최솟값)

전체 알고리즘은 아래 순서로 진행됩니다.

1. 두 개의 빈 데크 maxd, mind를 만들고, 왼쪽 포인터 i := 0, 결과 res := 1로 초기화합니다.
2. 오른쪽 포인터 j와 해당 값 a를 순회하며 다음을 반복합니다.
   • maxd가 비어 있지 않고 a가 maxd의 마지막 원소보다 크면 마지막 원소를 제거합니다.
   • mind가 비어 있지 않고 a가 mind의 마지막 원소보다 작으면 마지막 원소를 제거합니다.
   • a를 maxd와 mind의 뒤에 각각 추가합니다.
   • maxd[0] − mind[0] > limit, 즉 윈도우가 조건을 벗어나는 동안:
     • maxd[0]이 A[i]와 같다면 maxd의 앞 원소를 제거합니다.
     • mind[0]이 A[i]와 같다면 mind의 앞 원소를 제거합니다.
     • i를 1 증가시켜 윈도우의 왼쪽 경계를 축소합니다.
   • res를 res와 (j − i + 1) 중 더 큰 값으로 갱신합니다.
3. 순회가 끝나면 res를 반환합니다.

Python 구현 코드

from collections import deque

class Solution:
    def solve(self, A, limit):
        maxd = deque()   # 윈도우 내 최댓값 후보 (내림차순)
        mind = deque()   # 윈도우 내 최솟값 후보 (오름차순)
        i = 0            # 윈도우 왼쪽 경계
        res = 1

        for j, a in enumerate(A):
            # 새 값보다 작은 최댓값 후보는 제거
            while maxd and a > maxd[-1]:
                maxd.pop()
            # 새 값보다 큰 최솟값 후보는 제거
            while mind and a < mind[-1]:
                mind.pop()

            maxd.append(a)
            mind.append(a)

            # 윈도우 조건(max - min <= limit) 위반 시 왼쪽 축소
            while maxd[0] - mind[0] > limit:
                if maxd[0] == A[i]:
                    maxd.popleft()
                if mind[0] == A[i]:
                    mind.popleft()
                i += 1

            res = max(res, j - i + 1)

        return res

ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

실행 결과

입력:

[2, 4, 6, 10], 4

출력:

3

동작 과정 살펴보기

예제 입력 [2, 4, 6, 10], k = 4에 대해 코드가 어떻게 진행되는지 단계별로 확인해 보겠습니다.

1. j = 0 (a = 2): maxd = [2], mind = [2], 차이 0 ≤ 4 → res = 1
2. j = 1 (a = 4): 2보다 크므로 maxd = [4], mind = [2, 4], 차이 2 ≤ 4 → res = 2
3. j = 2 (a = 6): 4보다 크므로 maxd = [6], mind = [2, 4, 6], 차이 4 ≤ 4 → res = 3
4. j = 3 (a = 10): 6보다 크므로 maxd = [10], mind = [2, 4, 6, 10], 차이 8 > 4 → 윈도우 축소
   A[0] = 2가 mind의 맨 앞이므로 제거(i = 1), 여전히 차이 6 > 4
   A[1] = 4가 mind의 맨 앞이므로 제거(i = 2), 차이 4 ≤ 4로 만족 → 윈도우 길이 2, res는 3 유지

최종적으로 가장 긴 구간은 [2, 4, 6]이며 답은 3이 됩니다.

시간 복잡도

각 원소는 각 데크에 최대 한 번 삽입되고 한 번 제거되므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 데크에 저장되는 원소 수에 비례하여 O(n)입니다. 단순히 모든 구간을 검사하는 O(n²) 완전 탐색보다 훨씬 효율적입니다.