Two Pointer

투 포인터는 배열에서 두 개의 포인터를 사용해 문제를 해결하는 알고리즘입니다. 일반적으로 정렬된 배열에서 특정 조건을 만족하는 쌍을 찾거나, 부분 배열의 합을 구하는 등의 문제에 자주 사용됩니다. 투 포인터는 문제에 따라 적용 방식이 굉장히 다르기 때문에 문제를 풀어보며 설명하도록 하겠습니다.

BOJ 2470번: 두 용액 문제입니다. 두 용액을 섞어서 특성값이 최대한 0에 가깝게 만들어야 합니다. 가장 간단한 접근 방법은 \( O(N^2) \)으로 모든 쌍을 확인하는 것입니다. 당연히 시간 초과가 발생합니다. 이 방법의 문제는 굳이 확인할 필요가 없는 쌍까지 확인한다는 것입니다. 예를 들어, 가장 작은 용액과 가장 큰 용액을 섞어서 0보다 작은 값이 나왔다면, 특성값을 더 키워야 하는데, 가장 큰 용액보다 더 큰 용액이 존재하지 않으므로 가장 작은 용액을 섞는 것이 아니라 그 다음으로 작은 용액을 섞을 수 있습니다. 만약 가장 작은 용액과 가장 큰 용액을 섞어서 0보다 큰 값이 나왔다면, 특성값을 더 줄여야 하는데, 가장 작은 용액보다 더 작은 용액이 존재하지 않으므로 가장 가장 큰 용액을 섞는 것이 아니라 그 다음으로 큰 용액을 섞을 수 있습니다.

정리하면, 먼저 배열을 정렬합니다. 그리고 맨 처음을 가리키는 포인터 \( l \)과 맨 끝을 가리키는 포인터 \( r \)을 만듭니다. 그리고 \( l \)과 \( r \)이 가리키는 용액을 섞어서 특성값 a[l] + a[r]을 구합니다. 특성값의 합이 최솟값이라면 \( l \)과 \( r \)을 정답으로 저장합니다. 그리고 합이 0보다 작다면 특성값을 키워야 하므로 \( l \)을 오른쪽으로 한 칸 이동시킵니다. 합이 0보다 크다면 특성값을 줄여야 하므로 \( r \)을 왼쪽으로 한 칸 이동시킵니다. \( l \)과 \( r \)이 교차할 때까지 이 과정을 반복합니다.

이런 방식을 사용하면 모든 쌍을 확인하는 것이 아니라 \( O(N) \)의 시간복잡도로 모든 배열 원소를 한 번만 확인해서 처리할 수 있습니다. 배열이 정렬되어 있기 때문에 가능한 방법입니다. 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    int tmp = 2e9 + 1;
    pair<int, int> ans;

    int l = 0, r = n - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (abs(sum) < tmp) {
            tmp = abs(sum);
            ans = { a[l], a[r] };
        }

        if (sum < 0) l++;
        else  r--;
    }

    cout << ans.first << ' ' << ans.second;
}

이 문제에서는 포인터가 양쪽 끝에서 시작해 서로 교차할 때까지 이동하는 형태로 문제를 해결했습니다. 다른 문제에서는 두 포인터가 한 지점에서 시작해 같은 방향으로 이동하기도 합니다. 이 부분은 연습문제에 넣어 두었으니 풀어보시기 바랍니다.