[BOJ] C++ 2470 두 용액 - 투 포인터, 정렬

예제 입력 1

5
-2 4 -99 -1 98

예제 출력 1

-99 98

---

배열의 어떤 두 원소의 합 중 0과 가장 가까운 쌍을 찾는 문제이다.

투 포인터 알고리즘으로 풀 수 있다. 투 포인터 알고리즘이라 칭하면 어려워 보이지만 사실 그냥 포인터 두 개를 놓고 특정 기준에 따라 포인터를 옮겨가면서 배열을 탐색하는 알고리즘이다. 여기서 특정 기준을 찾는 게 문제의 난이도를 결정한다.

투 포인터 알고리즘으로 푼다고 생각했을 때 자세한 알고리즘은 어떻게 짤까? 우선 배열을 정렬하고, 포인터 두 개를 설정한다. 아직 이 포인터들을 차례로 둘지, 처음과 끝에 둘지 혹은 다른 방법으로 둘지는 생각하지 않은 상태이다. 이 포인터를 0과 가장 가까운 쌍을 찾을 수 있도록 옮기면서 배열을 탐색하면 된다. 그럼 여러 방법들을 생각해 보자.

1. 배열을 양수와 음수로 나누고 두 포인터를 양수, 음수 부분에 둔다.
   • 여러 기준을 설정해서 포인터를 아무리 옮겨봐도 완전 탐색과 다를 바가 없다. 투 포인터를 설정한 이점이 사라진다.
2. 배열의 처음과 끝에 각각 포인터를 둔다.
   • 이분 탐색처럼 포인터를 옮기면서 탐색하면 O(N)이 나온다.
   • 기준은 두 포인터가 가리키는 값의 합이 양수이면 그 합이 0에 가까워지려면 +의 기운이 약해져야 하므로 끝쪽 포인트(end_point)를 한 칸 줄이고(--) 음수이면 반대로 시작 쪽 포인트를 한 칸 늘리는 방식으로 깔끔하게 풀 수 있다. 예시를 한 번 그려봤는데 이해해 도움이 되길 바란다.

투 포인터의 기준을 생각하고 난 후의 구현은 아주 쉬운 편이다. 따로 알아야 할 테크닉은 없다.

/** 정렬 2470 두 용액 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<int> solve(N);
    for (int i = 0; i < N; i++)
        cin >> solve[i];

    sort(solve.begin(), solve.end());

    int point_start = 0, point_end = N - 1;
    int min = abs(solve[point_start] + solve[point_end]);
    int min_idx_st = 0, min_idx_end = N - 1;
    while (point_start < point_end)
    {
        int add = solve[point_start] + solve[point_end];
        if (abs(add) < min)
        {
            min = abs(add);
            min_idx_st = point_start;
            min_idx_end = point_end;
        }
        if (add > 0)
            point_end--;
        else
            point_start++;
    }
    cout << solve[min_idx_st] << " " << solve[min_idx_end];
}