📘 문제

문제링크 : https://www.acmicpc.net/problem/2470 (단계별로 풀어보기 : 투 포인터)

📝 문제 풀이

지난 번 문제에서 투포인터 알고리즘을 접해서 쉽게 풀 수 있었다. 일단 투포인터로 접근하기 위해서 수를 입력받고 배열을 정렬해준다. 그리고 양끝에서 시작해서 조건에 따라 문제의 조건을 만족하는 수의 위치를 찾아 저장해주고 마지막에 출력해주면 된다. 양끝에서 시작해서 수를 검사할 때 조건은
(왼쪽 포인터값 ptr1, 오른쪽 포인터값 ptr2.)

1. 두 수의 합이 0이면 두 수 출력 후 종료.
2. 두 수의 합이 0보다 작으면 ptr1 1 증가.
3. 두 수의 합이 0보다 크면 ptr2 1 감소.

   2,3번은 두 수의 합의 절댓값이 지금까지 가장 최소의 두 수의 합의 절댓값 보다 작을 시 포인터 저장.

으로 반복문을 돌려주면 된다. ❗️주의할 점은 주어진 수의 범위가 -1e10 ~ 1e10 이므로 두 수를 더했을 때 int 범위를 벗어날 수 있다는 점과 더해준 값을 비교할 때 절댓값을 적절히 사용해야 한다는 부분이다. 해당 부분에서 많이 실수를 범할 것 같다. 이렇게 풀면 시간복잡도는 O(nlogn) + O(n) 으로 O(nlogn)으로 해당 문제를 통과할 수 있다. (시간제한: 1초)

✏️ 알고리즘 스케치

💻 소스코드

#include <iostream>
#include <algorithm>
#include <cmath>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 2e10
#define ll long long
using namespace std;

void input(int *N, int **arr);
void solution(int N, int *arr);

int main()
{
    fastio;
    int N;
    int *arr;
    input(&N, &arr);
    sort(arr, arr + N);
    solution(N, arr);
    return 0;
}

void input(int *N, int **arr)
{
    cin >> *N;
    *arr = new int[*N];
    for (int i = 0; i < *N; i++)
        cin >> (*arr)[i];
}

void solution(int N, int *arr)
{
    int ptr1 = 0, ptr2 = N - 1;
    int solp1, solp2;
    ll closezero = INF;
    ll sum;
    while (ptr1 < ptr2)
    {
        sum = (ll)arr[ptr1] + arr[ptr2];
        if (abs(sum) < closezero)
        {
            closezero = abs(sum);
            solp1 = ptr1;
            solp2 = ptr2;
        }
        if (sum < 0)
            ptr1++;
        else if (sum > 0)
            ptr2--;
        else
        {
            cout << arr[ptr1] << " " << arr[ptr2];
            return;
        }
    }
    cout << arr[solp1] << " " << arr[solp2];
}