덱 코딩테스트: 슬라이딩 최댓값에서 만료와 제거를 구분하기

슬라이딩 최댓값을 단조 덱으로 구할 때는 창 밖으로 나간 인덱스의 만료와, 새 값이 뒤의 후보를 대신하는 제거를 구분해야 합니다. 두 작업은 덱의 서로 다른 끝에서 일어나며, 같은 값이 반복될 때는 인덱스가 없으면 어느 항목을 지웠는지 알 수 없습니다. [4,4,1,4]로 이 차이를 추적하고 힙 풀이와 복잡도도 비교합니다. PracHub의 Return the Maximum of Every Sliding Window는 연습용 질문 모음이며 실제 시험 문제를 보장하지 않습니다.

근거 범위. 공식 언어 문서는 라이브러리 동작의 근거입니다. 아래 불변식과 풀이의 정당성은 명시한 입력 계약에 따른 유도이며, 배열·그래프·시간축과 검산 코드는 이 글의 합성 교육 사례입니다. 후보자 보고나 특정 회사의 출제 형식은 사용하지 않았습니다.

먼저 정답과 상태를 고정하기 (Window state)

창 크기 k의 최댓값을 매 위치에서 출력하려면 덱에 값만 넣지 말고 인덱스를 저장합니다. 인덱스는 창에 남아 있는지 확인하고, 값은 뒤의 후보를 제거할지 비교하는 데 사용합니다. 두 작업을 같은 pop으로 뭉개면 중복 값에서 어떤 원소를 제거했는지 모호해집니다.

예를 들어 nums=[4,4,1,4], k=2의 답은 [4,4,4]입니다. 첫 번째 4가 인덱스 0에서 창 밖으로 나갈 때 인덱스 1의 4는 아직 유효합니다. 값만 저장했다면 앞의 4가 어느 원소인지 구별할 수 없습니다.

만료는 앞에서, 지배 제거는 뒤에서 (Expiry vs dominance)

현재 오른쪽 끝을 i라 할 때 창의 왼쪽은 i-k+1입니다. 덱 앞 인덱스가 이 값보다 작으면 유효 구간 밖이므로 앞에서 제거합니다. 이것이 만료(expiry)입니다. 그다음 새 값 nums[i]보다 작거나 같은 후보가 뒤에 있으면, 새 값은 더 최근에 있고 적어도 같은 크기라 그 후보의 미래 창을 모두 대체할 수 있습니다. 이를 뒤에서 제거하는 지배 제거라 부릅니다.

동률에서 <=를 쓰면 오래된 같은 값을 뒤에서 버리고 최신 인덱스만 보유합니다. <를 쓰면 동률을 보존합니다. 두 방식 모두 올바르지만, 만료 비교는 여전히 인덱스로 해야 합니다. 구현 예제는 <= 정책을 택합니다.

Python 구현과 경계 순서 (Index deque)

from collections import deque

def sliding_max(nums, k):
    if not 1 <= k <= len(nums):
        raise ValueError("k must be in [1, len(nums)]")
    q = deque()  # 인덱스, 값은 nums에서 조회
    out = []
    for i, value in enumerate(nums):
        while q and q[0] <= i - k:
            q.popleft()  # 창 밖 인덱스 만료
        while q and nums[q[-1]] <= value:
            q.pop()      # 새 값이 지배하는 후보 제거
        q.append(i)
        if i >= k - 1:
            out.append(nums[q[0]])
    return out

만료를 새 원소 삽입보다 먼저 처리해도, 뒤의 후보 제거보다 먼저 처리해도 같은 유효성을 유지할 수 있습니다. 중요한 것은 결과를 내기 전에 현재 창 밖 인덱스가 앞에 남아 있지 않게 하는 것입니다. k=1이면 매 창에 원소 하나만 남고, k=len(nums)이면 결과는 하나입니다. 빈 입력과 잘못된 k의 계약은 문제 설명에 맞춰 결정하세요.

최댓값의 위치까지 반환하는 변형에서는 동률 정책이 출력 계약의 일부가 됩니다. [7,7,2], k=2에서 최신 동률만 남기는 <= 정책은 오른쪽 인덱스를 반환하고, < 정책은 왼쪽 인덱스를 유지합니다. 값만 출력하면 두 구현의 결과가 같지만 위치를 반환하면 달라집니다. 문제에서 “가장 왼쪽” 또는 “가장 최근”을 요구하는지 확인하고, 출력 형식이 값인지 인덱스인지부터 테스트에 반영하세요. 새 배열의 값과 원래 위치를 함께 추적하는 변형에서도 이 선택이 필요합니다.

창이 완성되기 전에는 결과를 추가하지 않는 점도 따로 검사합니다. i < k-1인 동안은 출력하지 않고, 현재 인덱스를 삽입한 뒤 i >= k-1일 때 덱의 앞을 읽습니다. 이 조건은 첫 창이 만들어지는 시점을 정의합니다. 만료 인덱스가 최대 후보인 경우와 k=1을 함께 테스트하면, 현재 창에 포함되지 않는 값을 읽거나 첫 결과를 놓치는 오류를 쉽게 재현할 수 있습니다.

힙 풀이와 언제 차이가 나는가 (Lazy heap)

최대 힙을 쓸 때 Python heapq는 최소 힙이므로 값에 부호를 바꾸거나 별도 정렬 키를 둡니다. 힙은 임의 위치 삭제가 비싸기 때문에 오래된 항목을 지연 삭제하는 경우가 많습니다. 최상단을 읽기 전에 인덱스가 창 밖인지 반복 확인해야 stale entry가 답으로 노출되지 않습니다. 복잡도는 보통 O(n log n), 힙의 저장 공간도 최악 O(n)이 될 수 있습니다.

덱에서는 각 인덱스가 한 번 삽입되고 최대 한 번 제거되므로 O(n) 시간, O(k) 공간입니다. 다만 최대값 하나가 아니라 창마다 상위 여러 개가 필요하거나 중앙값을 추적하는 문제라면 덱 불변식만으로 해결되지 않습니다.

작은 오라클 테스트 (Oracle tests)

작은 배열 전체와 모든 유효 k에 대해 각 창을 직접 잘라 max와 대조합니다. 특히 [5,5,5], [9,1,2,3], 음수만 있는 배열, 반복되는 최댓값, k=1, k=n을 포함하세요. 덱 길이가 항상 k 이하라고 주장하기보다는 실제로는 지배 제거로 더 짧아질 수 있고, 항상 현재 창 안의 후보만 가진다고 설명하는 편이 정확합니다.

직접 풀어 볼 연습 자료 (Practice)

덱의 불변식으로 O(n)을 설명하기 (Amortized proof)

덱 인덱스는 왼쪽에서 오른쪽으로 증가하고, 해당 값은 앞에서 뒤로 감소하거나 동률입니다. <= 정책에서는 동률을 제거하므로 값도 엄격히 감소합니다. 맨 앞은 현재 창 안의 최댓값 후보이고, 뒤로 갈수록 값은 작지만 더 최근에 추가된 후보입니다. 뒤 후보가 새 값보다 작거나 같으면 새 인덱스는 더 오래 살아남고 값도 작지 않으므로 그 후보의 모든 미래 창을 대신할 수 있습니다.

복잡도는 중첩 while문만 보고 O(nk)라고 판단하지 않습니다. 각 인덱스는 정확히 한 번 append되고, 앞의 만료 또는 뒤의 지배 제거 중 한 방식으로 최대 한 번만 pop됩니다. 전체 연산 수는 삽입 n회와 제거 최대 n회 두 종류뿐이므로 O(n)이고, 어떤 한 창 안의 인덱스만 보유하므로 공간은 O(k)입니다. 새 값이 계속 증가하면 뒤에서 매번 제거되어 덱이 짧고, 계속 감소하면 덱이 최대 창 크기까지 길어집니다.

힙 지연 삭제가 헷갈리는 이유 (Stale entries)

힙에는 (값, 인덱스)를 저장합니다. 현재 창의 시작보다 오래된 최대 힙 top을 제거하고 나서 결과를 읽어야 합니다. top이 오래된 동안 안쪽에 숨겨진 stale 항목은 당장 정답을 바꾸지 않지만, 장시간 스트림에서는 힙 크기를 입력 길이만큼 키울 수 있습니다. 주기적으로 힙을 재구성하거나 indexed heap을 쓰는 방법도 있으나 구현 복잡도가 커집니다.

특히 동일한 값이 여러 번 들어오면 값만으로 삭제 대상을 찾을 수 없습니다. 인덱스가 없으면 4라는 값 하나를 제거할 때 그 4가 창 안의 값인지 밖의 값인지 구별되지 않습니다. 덱이나 힙 모두 중복 값을 그대로 담고, 만료 기준은 인덱스 또는 고유 ID로 결정해야 합니다.

다음 연습에서 설명할 한 가지 (Next exercise)

오늘은 Return the Maximum of Every Sliding Window를 풀면서 인덱스 기반 덱을 직접 구현해 경계 사례 하나와 시간·공간 복잡도를 소리 내어 설명해 보세요. Practice 자료는 연습을 위한 기록이며 실제 시험 문제를 예측하지 않습니다.

인덱스 표로 직접 검산하기 (Duplicate trace)

[4,4,1,4], k=2에서 i=1을 처리할 때 첫 번째 4의 인덱스 0은 아직 만료되지 않았지만, 새 4가 같은 최댓값이므로 뒤에서 지배됩니다. 이때 결과는 [4]입니다. i=2는 인덱스 1과 2로 이루어진 창입니다. 인덱스 1은 아직 유효하며 값 4가 정답입니다. i=3에서는 왼쪽 경계가 2가 되어 인덱스 1이 앞에서 만료됩니다. 값 1도 새 4에 뒤에서 제거됩니다. 출력은 [4,4,4]가 됩니다.

이 추적에서 주의할 점은 인덱스 0이 i=1에서 사라진 이유가 만료가 아니라 동률 정책이라는 것입니다. 같은 테스트라도 while nums[q[-1]] < value로 바꾸면 인덱스 0은 보존되고 다음 창에서 실제 만료됩니다. 결과는 같지만 덱 상태와 pop 이유는 다릅니다. 디버깅 로그에는 expired와 dominated를 다른 사건으로 기록하면 잘못된 경계 비교를 더 쉽게 찾을 수 있습니다.

입력 제약과 반환 계약 (Input contract)

k<=0이나 k>n을 오류로 처리할지 빈 목록으로 응답할지는 함수의 계약입니다. 코딩테스트에서는 대개 유효 입력을 준다는 가정이 있어도, 라이브 코딩이나 라이브러리 함수라면 명시적으로 다루는 편이 좋습니다. 모든 값이 음수일 때 초기 답을 0으로 두면 실제 창 최댓값보다 큰 가짜 값이 나올 수 있으므로 결과는 첫 창을 계산해 만들거나 덱의 앞을 직접 참조하세요. 위 구현은 그 점에서 안전합니다.

Sources and Further Reading

• CP-Algorithms: Minimum Stack / Minimum Queue — 창 최솟값을 단조 큐로 관리하는 불변식과 복잡도.
• Python collections.deque — 양 끝에서 빠르게 추가·제거하는 공식 자료형 문서.
• Python heapq — Python 최소 힙의 invariant와 루트 원소 문서.