Two Pointer로 최소 길이 부분합 구하기

네이버 블로그에 작성한 Two Pointer (2025-05-13)를 바탕으로 설명과 예제를 보완했다.

연속된 부분 배열의 합이 목표 이상이 되는 가장 짧은 길이를 찾는다고 하자. 시작점과 끝점의 모든 조합을 검사하면 O(N²)이다. 원소가 양수라는 조건을 이용하면 양 끝 인덱스를 뒤로 되돌리지 않고 탐색할 수 있다.

이 글은 원문에서 다룬 BOJ 1806 부분합의 양수 배열과 양수 목표 합을 기준으로 한다. 정렬하면 원래의 연속 구간이 달라지므로 이 문제에서는 정렬하지 않는다.

현재 구간을 하나로 유지하기

left와 right를 현재 구간의 양 끝으로 두고 sum을 그 구간의 합으로 유지한다.

1. 오른쪽 원소를 하나 추가한다.
2. 합이 목표 이상이면 현재 길이를 답 후보로 기록한다.
3. 왼쪽 원소를 빼면서 가능한 한 구간을 줄인다.
4. 합이 부족해지면 다음 오른쪽 원소를 추가한다.

예를 들어 [2, 3, 1, 2, 4, 3], 목표 7에서는 다음 후보를 만난다.

중간 후보를 모두 표시한 표는 아니다. 핵심은 조건을 만족할 때 왼쪽을 줄여 더 짧은 구간을 계속 찾는다는 점이다.

실행 가능한 C++17 풀이

#include <algorithm>
#include <iostream>
#include <vector>

int minimum_length(const std::vector<long long>& values, long long target) {
    const int n = static_cast<int>(values.size());
    int left = 0;
    int answer = n + 1;
    long long sum = 0;
    for (int right = 0; right < n; ++right) {
        sum += values[right];
        while (sum >= target) {
            answer = std::min(answer, right - left + 1);
            sum -= values[left++];
        }
    }
    return answer == n + 1 ? 0 : answer;
}

int main() {
    int n;
    long long target;
    if cin >> n >> target) return 0;
    std::vector<long long> values(n);
    for (auto& value : values) std::cin >> value;
    std::cout << minimum_length(values, target) << '\n';
}

입력은 문제의 범위를 만족한다고 가정한다. 합을 저장할 타입의 범위도 입력 제약에 맞춰 확인해야 한다.

c++ -std=c++17 -Wall -Wextra -pedantic two-pointer.cpp -o two-pointer
printf '6 7\n2 3 1 2 4 3\n' | ./two-pointer

출력은 2다. 합을 만족하는 구간이 없으면 0을 출력한다.

이중 반복문인데 O(N)인 이유

right는 각 원소를 한 번 추가한다. left도 앞으로만 이동하며 각 원소를 최대 한 번 제거한다. 안쪽 반복문의 총 실행 횟수가 N을 넘지 않으므로 전체 시간은 O(N), 입력 배열을 제외한 추가 공간은 O(1)이다.

음수가 있으면 같은 규칙을 적용할 수 없다

배열이 [1, -1, 5], 목표가 5라면 정답은 [5]의 길이 1이다. 위 절차는 전체 구간의 합이 5가 된 뒤 맨 앞 1을 빼서 합이 4가 되면 축소를 멈추므로 더 짧은 정답을 놓친다. 음수는 오른쪽 확장이 합을 키우고 왼쪽 축소가 합을 줄인다는 전제를 깨뜨린다.

Two Pointer라는 이름만 보고 적용하기보다, 포인터를 되돌리지 않아도 후보를 놓치지 않는 이유를 먼저 확인한다. 양 끝에서 가운데로 접근하는 정렬 배열의 두 수 합 문제와, 이 글의 같은 방향 윈도우는 이동 규칙도 다르다.