Algorithms/Sliding Window & Two Pointers

2.13.2 Two Pointers

개념

두 위치를 이동시키며 조건에 맞는 구간이나 원소 쌍을 찾는 방법입니다. 조건에 따라 어느 포인터를 움직여야 하는지 정합니다.

양수 수열의 연속 구간

모든 원소가 양수이면 오른쪽 끝을 오른쪽으로 옮겨 원소를 추가할 때 합이 커지고, 왼쪽 끝을 오른쪽으로 옮겨 원소를 제거할 때 합이 작아집니다. 합이 목표보다 작으면 오른쪽으로 늘리고, 합이 목표 이상이면 답을 갱신하면서 왼쪽 원소를 제거합니다.

[2,3,1,2,4,3][2,3,1,2,4,3]에서 합이 77 이상인 가장 짧은 구간은 [4,3][4,3]이며 길이는 22입니다. 음수가 포함되면 원소를 추가해도 합이 줄거나, 원소를 제거해도 합이 늘 수 있으므로 이 기준을 그대로 적용할 수 없습니다.

앞의 예에서 첫 네 원소 [2,3,1,2][2,3,1,2]의 합은 88입니다. 목표 77 이상이므로 길이 44를 기록하고 맨 앞의 22를 제거합니다. 합이 66으로 줄면 다시 오른쪽에 원소를 추가합니다. 한 시작점에서 목표를 만족하는 가장 짧은 구간을 확인한 뒤에는, 그 시작점을 유지하며 더 늘려도 길이가 더 길어질 뿐이므로 시작점을 앞으로 옮겨도 됩니다.

정렬된 수열의 두 수

합이 목표인 두 수를 찾을 때는 양 끝에서 시작합니다. 합이 작으면 왼쪽 위치를 오른쪽으로, 합이 크면 오른쪽 위치를 왼쪽으로 옮깁니다. 정렬되어 있으므로 각 이동이 합을 원하는 방향으로 바꿉니다.

정렬된 수열 [1,3,4,6,8][1,3,4,6,8]에서 합 1010을 찾는다면 양 끝의 합은 1+8=91+8=9입니다. 가장 큰 88과 더해도 부족하므로 11은 어느 원소와 짝지어도 답이 될 수 없어 왼쪽 포인터를 옮깁니다. 다음 합 3+8=113+8=11은 너무 큽니다. 현재 남은 가장 작은 33과 더해도 크므로 88을 제외합니다. 이런 근거로 한쪽씩 제외하면 모든 쌍을 비교하지 않고도 답을 찾을 수 있습니다.

복잡도

원소 수를 NN이라고 합니다. 두 포인터가 각각 앞으로 최대 NN번 이동합니다.

연산시간복잡도공간복잡도
조건을 만족하는 최소 구간 탐색O(N)O(N)입력 O(N)O(N), 추가 O(1)O(1)

예제

문제

합이 SS 이상인 연속 구간 중 가장 짧은 길이를 구하여라.

입력

첫째 줄에 원소 수 NN과 목표 합 SS가 공백을 사이에 두고 주어진다. 1≤N≤1 0001\le N\le1\,000; 1≤S≤1 000 0001\le S\le1\,000\,000이다.

둘째 줄에 수열의 원소 a1,a2,…,aNa_1,a_2,\ldots,a_N이 공백을 사이에 두고 주어진다. 1≤ai<10 0001\le a_i<10\,000이다.

출력

최소 길이를 출력한다. 조건을 만족하는 구간이 없으면 00을 출력한다.

예제 입력

6 7
2 3 1 2 4 3

예제 출력

2

예제 코드

C++20

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

using namespace std;

vector<int> v;

int main() {
    int n, target, i, l, r, s, ans;

    cin >> n >> target;
    v.resize(n);
    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }
    l = 0;
    s = 0;
    ans = n + 1;
    for (r = 0; r < n; ++r) {
        s += v[r];
        while (s >= target) {
            ans = min(ans, r - l + 1);
            s -= v[l];
            ++l;
        }
    }
    if (ans == n + 1) ans = 0;
    cout << ans << '\n';
}