투 포인터와 슬라이딩 윈도 - 구간을 밀며 보기

이 장에서 배우는 것

앞 장에서 키를 기준으로 값을 세고 찾는 방법을 익혔다. 이번에는 리스트 안에서 위치를 움직이며 답을 찾는다. 같은 구간을 처음부터 다시 계산하지 않고, 경계가 바뀐 부분만 반영하는 것이 핵심이다. 다만 경계를 움직인다고 해서 언제나 올바른 답을 얻는 것은 아니다. 어떤 후보를 버려도 되는지 설명할 수 있어야 한다.

투 포인터(two pointers)는 두 위치를 움직여 후보를 좁히는 방법이다. 슬라이딩 윈도(sliding window)는 연속 구간의 경계를 움직이면서 그 구간의 합이나 개수 같은 정보를 유지하는 방법이다. 두 방법은 함께 쓰이는 경우가 많지만, 두 위치가 항상 연속 구간을 뜻하는 것은 아니다.

• 정렬된 배열에서 두 수의 합을 찾고, 포인터를 움직이는 이유를 설명한다.
• 반열린 구간과 구간 합의 불변식을 이용해 가변 길이 윈도를 구현한다.
• 원소가 음수일 때 같은 풀이가 실패하는 반례를 만든다.
• 조건을 만족하는 가장 짧은 구간을 구하고, 작은 입력 전체에서 완전 탐색과 대조한다.

문제 상황

작은 작업장의 자재 담당자가 두 가지 확인 기능을 만들려고 한다. 첫 번째는 길이가 정렬되어 있는 자재 목록에서 두 개를 골라 정해진 길이를 만드는 기능이다. 서로 다른 두 자재를 골라야 하며, 같은 길이의 자재가 여러 개 있다면 각각 따로 사용할 수 있다. 합이 맞는 조합 하나만 찾으면 된다.

길이 목록이 [1, 3, 4, 6, 8, 11]이고 목표가 10이면 길이 4와 6을 고를 수 있다. 가능한 모든 쌍을 검사해도 답을 얻지만, 정렬되어 있다는 조건을 활용하면 이미 결과를 예상할 수 있는 쌍을 건너뛸 수 있다.

두 번째는 시간대별 입고 수량을 확인하는 기능이다. 기록 순서는 시간 순서이므로 바꿀 수 없다. 연속된 시간대의 입고량 합이 목표 이상이 되는 구간 중 길이가 가장 짧은 것을 찾는다. 입고가 없는 시간대는 0으로 기록하고, 반품은 별도로 관리하므로 이 기록에는 음수가 없다.

입고 기록이 [2, 1, 4, 1, 2, 6, 1]이고 목표가 7이면 [2, 6]이라는 길이 2의 구간을 선택할 수 있다. 길이 1인 구간에는 7 이상의 값이 없으므로 답은 2다. 목표에 도달하는 구간이 없으면 0을 반환한다. 빈 구간은 답으로 인정하지 않으며 목표는 양수라고 정한다.

두 기능 모두 위치 두 개를 사용하지만 위치의 뜻은 다르다. 첫 번째의 두 위치는 선택할 원소 두 개를 가리킨다. 그 사이의 원소를 모두 선택하는 것이 아니다. 두 번째의 두 위치는 선택한 연속 구간의 양 끝을 나타낸다. 이 차이를 먼저 정해야 코드의 조건도 분명해진다.

정렬된 배열에서는 양 끝에서 좁힌다

자재 목록의 첫 위치를 left, 마지막 위치를 right라고 하자. 두 원소의 합이 목표보다 작으면 왼쪽 위치를 오른쪽으로 한 칸 옮긴다. 합이 목표보다 크면 오른쪽 위치를 왼쪽으로 한 칸 옮긴다. 합이 같으면 그 두 값을 반환한다.

이 이동의 근거는 정렬 순서에 있다. 현재 합이 목표보다 작다고 하자. 현재 왼쪽 값에 지금보다 작은 오른쪽 값을 더해도 합은 커지지 않는다. 따라서 현재 왼쪽 원소로 만들 수 있는 남은 쌍에는 답이 없다. 왼쪽 원소를 후보에서 제외해도 된다.

반대로 현재 합이 목표보다 크면, 현재 오른쪽 값에 지금보다 큰 왼쪽 값을 더해도 합은 작아지지 않는다. 따라서 현재 오른쪽 원소를 쓰는 남은 쌍을 제외할 수 있다. 두 경우 모두 단순히 답에 가까워 보이는 방향을 고르는 것이 아니다. 제외하는 후보가 답이 될 수 없음을 확인하고 움직인다.

목표 10을 만드는 두 자재를 찾는 과정

왼쪽 값	오른쪽 값	합	판단
1	11	12	오른쪽을 줄인다
1	8	9	왼쪽을 늘린다
3	8	11	오른쪽을 줄인다
3	6	9	왼쪽을 늘린다
4	6	10	두 값을 반환한다

이 탐색의 불변식은 “아직 찾지 못한 정답 쌍이 있다면 두 위치 사이에 남아 있다”이다. 처음에는 모든 원소가 범위 안에 있다. 각 이동은 답이 될 수 없는 한쪽 끝만 제거하므로 이 성질이 유지된다. 두 위치가 만나면 서로 다른 두 원소를 고를 수 없으므로 탐색을 끝낸다.

반복 조건이 left < right인 이유도 여기에 있다. 같은 위치를 두 번 고르는 것은 허용하지 않는다. 값이 같은 원소를 고르는 것과 같은 위치를 두 번 고르는 것은 다르다. 예를 들어 [5, 5]에서는 서로 다른 두 위치로 합 10을 만들 수 있다.

각 반복에서 적어도 한 위치가 안쪽으로 한 칸 이동한다. 두 위치 사이의 간격은 처음에 n보다 작고 계속 줄어드므로 탐색 시간은 O(n), 추가 공간은 O(1)이다. 입력이 정렬되지 않았다면 이 근거를 사용할 수 없다. 먼저 정렬한다면 일반적인 정렬 비용 O(n log n)이 더해진다. 원래 위치를 출력해야 하는 문제에서는 값과 원래 위치를 함께 보관해야 한다.

가변 길이 윈도는 합과 경계를 함께 유지한다

입고 기록은 시간 순서를 지켜야 하므로 정렬할 수 없다. 대신 오른쪽 끝에 새 기록을 포함하고, 합이 충분하면 왼쪽 끝의 기록을 제외하며 구간을 줄인다. 길이를 미리 고정하지 않고 합에 따라 구간 크기를 바꾸므로 가변 길이 윈도라고 부른다.

코드에서는 구간을 [left, right)로 나타낸다. 왼쪽 위치는 포함하고 오른쪽 위치는 포함하지 않는 반열린 구간이다. 구간 길이는 right - left다. 두 위치가 같으면 빈 구간이다. 오른쪽 위치를 원소 개수와 같은 값까지 사용할 수 있어 마지막 원소를 포함하는 구간도 같은 규칙으로 표현할 수 있다.

total에는 현재 구간의 합을 저장한다. 오른쪽 원소를 포함할 때 그 값을 더하고, 왼쪽 원소를 제외할 때 그 값을 뺀다. 이때 유지할 첫 번째 불변식은 total은 언제나 현재 구간의 합과 같다는 것이다. 계산한 합과 경계가 서로 다른 구간을 가리키면 이후 판단은 모두 근거를 잃는다.

목표가 7인 예시를 손으로 따라가 보자. 표의 오른쪽 위치는 포함하지 않는 경계다. 합이 목표 이상이면 현재 길이를 답 후보로 기록한 뒤 왼쪽 원소를 뺀다. 합이 목표보다 작아질 때까지 이 과정을 반복한다.

입고 기록에서 오른쪽을 확장하고 왼쪽을 줄이는 과정

오른쪽 경계	추가 직후 합	왼쪽을 줄인 과정	축소 후 상태
1	2	목표 미달	[0, 1), 합 2
2	3	목표 미달	[0, 2), 합 3
3	7	길이 3 기록, 2 제외	[1, 3), 합 5
4	6	목표 미달	[1, 4), 합 6
5	8	길이 4와 3 확인, 1과 4 제외	[3, 5), 합 3
6	9	길이 3과 2 확인, 1과 2 제외	[5, 6), 합 6
7	7	길이 2 확인, 6 제외	[6, 7), 합 1

오른쪽 경계가 6일 때 합은 9다. 먼저 길이 3인 [1, 2, 6]을 확인한다. 왼쪽의 1을 빼도 합이 8이므로 길이 2인 [2, 6]도 확인한다. 다시 2를 빼면 합이 6이 되어 목표에 미달한다. 한 번의 확장에서 왼쪽 경계가 여러 번 움직일 수 있으므로 축소에는 조건문 하나가 아니라 반복문이 필요하다.

정확성을 이해하려면 왼쪽 경계를 버리는 순간을 보아야 한다. 어떤 왼쪽 위치에서 현재 구간이 목표를 만족했다면 그 길이를 이미 답 후보로 기록한다. 나중에 오른쪽 끝을 더 늘려 같은 왼쪽 위치를 쓰는 구간은 더 길다. 따라서 최솟값을 찾는 데 그 왼쪽 위치를 다시 사용할 필요가 없다.

아직 남아 있는 시작점 중에서는 합이 목표 이상인 동안 하나씩 길이를 확인한다. 합이 목표보다 작아지면 축소를 멈춘다. 모든 원소가 0 이상이므로 왼쪽에서 원소를 더 빼도 합이 커질 수 없기 때문이다. 현재 시작점에서도 부족하다면 그보다 오른쪽의 시작점에서도 부족하다.

이를 두 번째 불변식으로 정리할 수 있다. 이미 지나간 시작점은 답 후보로 처리되어 있고, 축소가 끝난 현재 구간은 목표에 미달한다. 처음에는 빈 구간의 합이 0이라 성립한다. 오른쪽 확장 뒤 필요한 길이를 모두 기록하고 목표에 미달할 때까지 축소하면 다시 성립한다. 마지막 오른쪽 경계까지 처리하면 필요한 후보를 빠뜨리지 않고 최솟값을 얻는다.

반복문 안에 반복문이 있어도 시간은 O(n)이다. 오른쪽 경계는 n번 이동하고 왼쪽 경계도 전체 실행 동안 최대 n번 이동한다. 안쪽 반복 횟수를 바깥 반복마다 n번으로 계산하면 실제로 일어나지 않는 이동까지 세게 된다. 입력 리스트를 제외한 추가 공간은 합, 경계, 최솟값을 저장하는 O(1)이다.

조건을 바꾸면 이동의 근거도 바뀐다

입고량에 0이 있어도 앞의 논리는 유지된다. 0을 더하거나 빼면 합이 그대로지만, 합이 반대 방향으로 바뀌지는 않는다. 목표가 양수이므로 빈 구간까지 줄어들면 합은 0이고 축소 반복은 끝난다. 따라서 이 구현은 양수만이 아니라 0 이상의 정수 전체를 다룬다.

음수가 포함되면 상황이 달라진다. [1, -1, 5]에서 목표가 5라고 하자. 같은 이동 규칙을 적용하면 마지막 원소까지 포함한 합이 5이므로 길이 3을 기록한다. 왼쪽의 1을 빼면 합이 4가 되어 축소를 멈춘다. 그러나 이어서 -1도 빼면 합이 5로 증가하고 길이 1인 정답 [5]이 나타난다.

실패의 원인은 합이 부족하다는 이유만으로 뒤의 시작점을 더 확인하지 않은 데 있다. 음수를 빼면 합이 커질 수 있으므로, 현재 구간이 목표에 미달한다는 사실만으로 더 짧은 구간도 미달한다고 판단할 수 없다. 완성 코드에서는 이런 입력을 조용히 처리하지 않고 오류로 거절한다.

음수의 존재가 모든 두 포인터 풀이를 막는 것은 아니다. 정렬된 배열에서 두 수의 합을 찾는 앞의 풀이는 음수가 있어도 정렬 순서를 이용한 제외 근거가 유지된다. 적용 가능성은 기법 이름이 아니라 각 이동의 근거로 판단해야 한다. 음수가 있는 연속 구간의 최단 길이 문제에는 별도의 풀이가 필요하다.

조건이 바뀌는 경우도 주의해야 한다. “합이 목표 이상”을 “합이 목표와 같음”으로 바꾸거나, 최단 길이 대신 구간 개수를 묻는다면 답을 기록하는 방식부터 다시 검토해야 한다. 경계를 움직이는 모양이 비슷하더라도 같은 코드를 그대로 옮길 수 있는 것은 아니다.

완전 탐색은 모든 시작점에서 오른쪽 끝을 하나씩 늘려 합을 누적한다. 구간마다 합을 처음부터 다시 구하지 않으므로 시간은 O(n²), 추가 공간은 O(1)이다. 작은 입력에서는 이처럼 이동에 관한 가정이 적은 풀이를 기준 답으로 삼기 좋다. 비교용 완전 탐색은 합이 목표에 도달해도 중간에 멈추지 않고 모든 구간을 확인하도록 작성한다.

완성 코드

다음 내용을 main.py로 저장한다. 두 자재 찾기와 입고 구간 찾기를 실행한 뒤, 작은 입력 전체에서 빠른 풀이를 느린 풀이와 비교한다. 입고 기록은 문자열을 파일처럼 읽도록 만들어 코딩 테스트식 입력 처리를 흉내 낸다. 실제 표준 입력을 기다리는 코드는 없다.

전수 대조에서는 길이 0부터 6까지, 원소 값 0부터 3까지인 모든 리스트를 만든다. 각 리스트에 목표 1부터 8까지를 적용한다. 0의 연속, 중복 값, 빈 리스트, 도달 불가능한 목표가 함께 포함된다. 난수를 사용하지 않으므로 실행 결과는 항상 같다.

from io import StringIO
from itertools import product


def find_pair(values, target):
    # values는 오름차순으로 정렬되어 있어야 한다.
    left = 0
    right = len(values) - 1

    while left < right:
        total = values[left] + values[right]
        if total == target:
            return values[left], values[right]
        if total < target:
            left += 1
        else:
            right -= 1

    return None


def has_pair_brute(values, target):
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] + values[right] == target:
                return True
    return False


def shortest_window(values, target):
    if target <= 0:
        raise ValueError("목표는 양수여야 한다")
    if any(value < 0 for value in values):
        raise ValueError("입고량은 0 이상이어야 한다")

    left = 0
    total = 0
    best = len(values) + 1

    for right, value in enumerate(values, start=1):
        total += value

        while total >= target:
            best = min(best, right - left)
            total -= values[left]
            left += 1

    return 0 if best == len(values) + 1 else best


def shortest_window_brute(values, target):
    best = len(values) + 1

    for left in range(len(values)):
        total = 0
        for right in range(left, len(values)):
            total += values[right]
            if total >= target:
                best = min(best, right - left + 1)

    return 0 if best == len(values) + 1 else best


def read_example():
    source = StringIO("7 7\n2 1 4 1 2 6 1\n")
    n, target = map(int, source.readline().split())
    values = list(map(int, source.readline().split()))

    if len(values) != n:
        raise ValueError("기록 개수가 맞지 않는다")

    return values, target


def verify_all():
    checked = 0

    for size in range(7):
        for items in product(range(4), repeat=size):
            values = list(items)
            ordered = sorted(values)

            for target in range(1, 9):
                fast = shortest_window(values, target)
                slow = shortest_window_brute(values, target)
                if fast != slow:
                    raise AssertionError(
                        ("구간 불일치", values, target, fast, slow)
                    )

                pair = find_pair(ordered, target)
                exists = has_pair_brute(ordered, target)
                if (pair is not None) != exists:
                    raise AssertionError(
                        ("쌍 존재 여부 불일치", ordered, target)
                    )
                if pair is not None and sum(pair) != target:
                    raise AssertionError(
                        ("쌍의 합 불일치", ordered, target, pair)
                    )

                checked += 1

    return checked


def main():
    materials = [1, 3, 4, 6, 8, 11]
    print("자재 쌍:", find_pair(materials, 10))

    values, target = read_example()
    print("최단 구간 길이:", shortest_window(values, target))
    print("완전 탐색 길이:", shortest_window_brute(values, target))

    checked = verify_all()
    print("전수 대조 통과:", checked, "건")


if __name__ == "__main__":
    main()

줄별 해설

StringIO는 문자열에 readline()을 적용할 수 있게 한다. product는 지정한 값들로 만들 수 있는 모든 나열을 생성한다. 예를 들어 product(range(4), repeat=2)는 길이가 2이고 각 값이 0부터 3까지인 16개 나열을 만든다. 길이가 0이면 빈 나열 하나를 만든다.

find_pair의 left = 0과 right = len(values) - 1은 실제 원소의 위치를 가리킨다. 빈 리스트에서는 오른쪽 위치가 -1이지만 반복 조건이 처음부터 거짓이므로 원소에 접근하지 않는다. 합이 같을 때 반환하는 것은 위치가 아니라 값 두 개다. 이 함수는 입력을 직접 정렬하지 않으므로 호출하는 쪽에서 정렬 조건을 지켜야 한다.

has_pair_brute는 비교 기준이다. 두 번째 위치를 left + 1부터 시작해 같은 원소를 두 번 고르지 않고, 같은 쌍을 순서만 바꾸어 중복 검사하지 않는다. 두 풀이가 서로 다른 정답 쌍을 고를 수 있으므로 전수 대조에서는 반환한 쌍 자체가 아니라 정답의 존재 여부를 비교한다.

shortest_window의 앞부분은 풀이의 전제를 검사한다. 목표가 양수가 아니거나 음수가 섞여 있으면 ValueError를 발생시킨다. 음수 검사에 O(n)이 걸리지만 전체 시간은 여전히 O(n)이다. 비교용 완전 탐색 함수는 전수 대조에서 같은 양수 목표를 받으며, 음수의 반례를 확인할 때도 사용할 수 있다.

best = len(values) + 1은 아직 답을 찾지 못했다는 표시다. 유효한 구간 길이는 리스트 길이를 넘을 수 없으므로 실제 답과 구별된다. 마지막 줄에서 이 값이 그대로라면 0을 반환한다. 처음부터 0을 저장하고 최솟값을 구하면 어떤 양수 길이로도 갱신되지 않는 문제가 생긴다.

enumerate(values, start=1)의 right는 이번에 추가할 원소의 인덱스가 아니라, 추가한 뒤의 오른쪽 경계다. 첫 번째 값이 추가되면 경계가 1이 되어 구간은 [0, 1)이 된다. 따라서 길이에 1을 더하지 않고 right - left를 사용한다.

total += value는 오른쪽 확장에 해당한다. 이어지는 반복문에서는 먼저 현재 길이를 기록하고, 그다음 왼쪽 값을 뺀 뒤 경계를 옮긴다. 이 세 줄의 순서는 현재 조건을 만족한 구간을 기록한다는 뜻을 담고 있다. 축소를 마치면 현재 합은 목표보다 작아지고 다음 오른쪽 값을 기다린다.

shortest_window_brute에서는 right가 포함되는 마지막 원소의 인덱스다. 그래서 길이는 right - left + 1이다. 두 함수의 변수 이름이 같아도 경계 정의는 다를 수 있다. 코드를 읽을 때는 이름보다 반복 범위와 원소 접근을 확인해야 한다.

read_example은 첫 줄의 기록 개수와 목표를 읽고 둘째 줄을 정수 리스트로 바꾼다. 기록 개수도 검사하므로 예시 문자열을 수정하다가 값을 빠뜨리면 오류로 드러난다. 이 예시 입력은 기록이 둘째 줄에 모여 있는 형식으로 정했다.

verify_all은 구간 풀이에는 원래 순서의 리스트를, 두 자재 풀이에는 정렬한 리스트를 전달한다. 서로 다른 문제의 전제를 각각 지키는 것이다. 불일치가 있으면 입력과 결과를 담아 오류를 발생시키므로 실패한 사례를 바로 재현할 수 있다.

검사 건수는 (1 + 4 + 16 + 64 + 256 + 1024 + 4096) × 8인 43,688건이다. 한 건마다 구간 최단 길이와 쌍 존재 여부를 모두 확인한다. 이 유한한 검사는 구현 실수를 찾는 근거이며, 임의의 큰 입력에 대한 정확성은 앞서 설명한 불변식과 후보 제외 논리가 뒷받침한다.

실행 결과

macOS나 Linux에서 Python 3.12 이상으로 실행한다. 첫 명령은 문법과 컴파일 단계의 경고를 확인하고, 둘째 명령은 예시와 전수 대조를 실행한다. 첫 명령이 성공하면 별도 출력은 없다.

python3 -W error -m py_compile main.py
python3 main.py

예상 출력은 다음과 같다.

자재 쌍: (4, 6)
최단 구간 길이: 2
완전 탐색 길이: 2
전수 대조 통과: 43688 건

완성 프로그램에는 느린 기준 풀이와 전수 대조가 포함되어 있다. 따라서 프로그램 전체의 실행 비용을 최단 구간 함수 하나의 O(n)과 혼동하면 안 된다. 실제 문제 제출에서는 필요한 빠른 함수와 입력 처리만 사용하고, 전수 대조는 개발 중 검증에 활용한다.

실무에서 자주 틀리는 것

연속 구간 문제의 입력을 정렬한다

두 자재를 고를 때는 정렬을 활용할 수 있지만 시간대별 기록을 정렬하면 이웃 관계가 바뀐다. 원래 떨어져 있던 기록이 붙어 존재하지 않던 연속 구간을 만들 수 있다.

틀린 코드는 다음과 같다.

values = sorted(values)
answer = shortest_window(values, target)

연속 구간은 원래 순서를 유지해 계산한다.

answer = shortest_window(values, target)

정렬을 적용하기 전에는 답이 원소의 순서에 의존하는지 확인한다. 정렬은 단순한 준비 작업이 아니라 입력의 의미를 바꾸는 연산이기도 하다.

한 번만 줄이고 다음 원소로 넘어간다

합이 목표 이상일 때 한 번만 축소하면 같은 오른쪽 끝에서 더 짧은 구간을 놓친다. 목표가 7인 [1, 1, 7]에서는 마지막 원소 하나만 남길 때까지 확인해야 한다.

틀린 코드는 다음과 같다.

if total >= target:
    best = min(best, right - left)
    total -= values[left]
    left += 1

조건을 만족하는 동안 반복해 줄인다.

while total >= target:
    best = min(best, right - left)
    total -= values[left]
    left += 1

이 반복이 길어 보여도 왼쪽 경계는 되돌아가지 않는다. 한 원소는 왼쪽에서 최대 한 번 제외된다.

왼쪽 경계를 먼저 옮기고 값을 뺀다

현재 제외할 값은 이동 전의 왼쪽 위치에 있다. 경계를 먼저 옮기면 다른 값을 빼므로 저장한 합과 실제 구간이 달라진다. 마지막 위치에서는 범위를 벗어난 접근도 생길 수 있다.

틀린 코드는 다음과 같다.

left += 1
total -= values[left]

현재 값을 먼저 빼고 경계를 옮긴다.

total -= values[left]
left += 1

경계를 갱신하는 코드에서는 갱신 직후에도 저장한 합이 새 구간과 일치하는지 확인한다. 짧은 예시에서 직접 합을 더해 보면 이런 오류를 찾기 쉽다.

음수 검사를 빼고 적용 범위를 넓힌다

전제 검사를 지우는 것만으로 음수를 지원할 수는 없다. 합이 부족하면 축소를 멈춘다는 판단 자체가 음수에서 성립하지 않는다.

틀린 사용은 다음과 같다.

# 음수 검사를 삭제한 함수를 그대로 사용한다고 가정한다.
answer = shortest_window([1, -1, 5], 5)

작은 음수 입력의 답을 확인하려면 모든 구간을 조사하는 기준 풀이를 사용할 수 있다.

answer = shortest_window_brute([1, -1, 5], 5)
# answer는 1이다.

큰 음수 입력까지 빠르게 처리해야 한다면 다른 알고리즘을 설계해야 한다. 완전 탐색으로 바꾸는 것은 작은 입력을 위한 선택이며, 실행 시간을 다시 계산해야 한다.

한눈에 보기

두 위치를 움직일 때 확인할 전제와 비용

풀이	필요한 조건	이동의 근거	시간 / 추가 공간
두 수의 합	정렬된 배열, 다른 두 위치	한쪽 끝을 쓰는 쌍 전체를 제외	O(n) / O(1)
최단 합 구간	원소 0 이상, 목표 양수	확장은 합을 줄이지 않고 축소는 늘리지 않음	O(n) / O(1)
구간 완전 탐색	원소 부호 제한 없음, 목표 양수	모든 시작점과 끝점 확인	O(n²) / O(1)

구현 전에는 두 위치가 원소를 가리키는지 경계를 가리키는지 정한다. 이어서 한 번 이동할 때 무엇을 버리는지, 버린 후보를 나중에 다시 볼 필요가 없는지 설명한다. 마지막으로 빈 입력, 0, 중복 값, 답이 없는 경우를 느린 풀이와 비교한다. 이동 횟수가 적다는 사실만으로 정확성이 보장되지는 않는다.

연습 문제

1. 정렬된 자재 목록이 [2, 2, 5, 9]이고 목표가 4다. 두 포인터가 검사하는 값의 쌍을 순서대로 적고, 같은 값 두 개를 사용할 수 있는 이유를 설명하라.
2. 입고 기록이 [0, 2, 0, 5]이고 목표가 5다. 마지막 원소를 추가한 직후부터 축소가 끝날 때까지 구간 길이와 합의 변화를 적어라. 최단 길이도 구하라.
3. 목표가 5인 기록 [4, -3, 5]에 음수 검사를 제거한 윈도 풀이를 적용하면 어떤 길이가 나오는지 구하라. 실제 답과 달라지는 순간을 설명하라.
4. 최단 길이와 함께 구간의 왼쪽 경계와 오른쪽 경계도 반환하도록 함수를 수정하라. 길이가 같으면 먼저 발견한 구간을 유지하고, 답이 없으면 (0, -1, -1)을 반환하라. 오른쪽 경계는 포함하지 않는다.

정답과 해설

1. 검사하는 값의 쌍은 (2, 9), (2, 5), (2, 2)다. 앞의 두 합은 목표보다 크므로 오른쪽 위치를 줄인다. 마지막 두 값은 같지만 위치가 0과 1로 서로 다르다. 따라서 합 4를 만드는 유효한 쌍이다. 값의 중복을 금지한 문제가 아니라 위치의 재사용을 금지한 문제다.

2. 마지막 원소를 추가하면 구간은 [0, 4)이고 합은 7이다. 길이 4를 기록하고 0을 빼면 합은 7이다. 길이 3을 기록하고 2를 빼면 합은 5다. 길이 2를 기록하고 0을 빼도 합은 5다. 길이 1을 기록하고 5를 빼면 합이 0이 되어 멈춘다. 답은 1이다. 합이 변하지 않아도 경계는 전진하므로 반복은 끝난다.

3. 전체 합이 6이 되는 순간 길이 3을 기록한다. 이어서 왼쪽의 4를 빼면 합이 2가 되어 멈추므로 결과는 3이다. 실제로는 마지막 원소 [5]만 선택한 길이 1이 답이다. 합이 2일 때 -3을 더 제외하면 합이 5가 되지만, 음수 없는 경우의 중단 규칙이 이 후보를 막는다.

4. 합과 경계를 움직이는 규칙은 유지하고, 더 짧은 길이를 발견할 때 경계를 함께 저장한다. 같은 길이에서 갱신하지 않도록 비교에 <를 사용한다. 다음 함수도 원소가 0 이상이고 목표가 양수인 경우를 다룬다.

   def shortest_window_with_bounds(values, target):
       if target <= 0:
           raise ValueError("목표는 양수여야 한다")
       if any(value < 0 for value in values):
           raise ValueError("입고량은 0 이상이어야 한다")
   
       left = 0
       total = 0
       best = len(values) + 1
       bounds = (-1, -1)
   
       for right, value in enumerate(values, start=1):
           total += value
           while total >= target:
               length = right - left
               if length < best:
                   best = length
                   bounds = (left, right)
               total -= values[left]
               left += 1
   
       if best == len(values) + 1:
           return 0, -1, -1
       return best, bounds[0], bounds[1]
   

   본문의 입고 기록과 목표 7을 넣으면 (2, 4, 6)을 반환한다. 인덱스 4부터 6 직전까지인 [2, 6]이다. 이후 [6, 1]도 길이 2로 발견되지만 먼저 저장한 구간을 유지한다. 검증할 때는 반환 길이뿐 아니라 경계 차이가 길이와 같은지, 해당 구간의 합이 목표 이상인지도 함께 확인한다.