[백준] 2470번 두 용액 (C++)

문제 링크

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제 설명

N개의 숫자를 무작위 순서로 입력 받는다.

각 숫자의 범위는 -1,000,000,000 ~ 1,000,000,000 이며, N개의 숫자들 중 2개의 숫자를 선택했을 때

그 합의 절댓값이 0과 가장 가까운 두 수를 출력한다.

 

사고 과정

처음에는 이분 탐색으로 풀고자 하였다.

하지만 기존 이분 탐색 문제들에서는 하나의 값에 대해 탐색하는 과정이 필요했지만,

해당 문제의 경우 두 개의 값을 탐색해야 했다.

따라서 투 포인터를 사용하여 두 수의 합이 0에 가까운 값을 찾아야겠다는 생각이 들었다.

 

입력 받은 값들을 배열에 오름차순으로 정렬하고 인덱스를 활용하여 값을 찾고자 하였다.

Left와 Right 변수를 설정하여 두 수의 합에 따라 Left와 Right를 옮기고자 하였고,

두 수의 합이 이전의 합에 비해 작을 경우 출력될 결과값을 저장하고 있는 변수를 갱신하였다.

 

가장 어려웠던 점은 Left와 Right 변수를 어떻게 옮기느냐였다.

두 수의 합이 이전에 구했던 합보다 작다면 결과값을 갱신한 후에

Left를 증가시켜야 할 지 아니면 Right를 감소시켜야 할지,

이전에 구했던 합보다 크다면 결과값은 그대로 유지한 채

Left를 증가시켜야 하는지 Right를 감소시켜야 하는지 판단하는 것이 어려웠다.

 

해결 방법

단순하게 결과값 갱신 여부에 따라 Left 및 Right 변수를 수정해서는 안된다는 것을 깨달았다.

위 그림에서 temp는 현재 left와 right 인덱스에 해당하는 배열의 값을 합친 값을 의미하며

sum은 '현재까지' 두 수의 합을 구한 값들 중 절댓값이 최소인 값을 의미한다.

위에서 확인할 수 있듯이 sum 변수의 갱신 여부와 상관없이,

temp, 즉 현재 left와 right에 해당하는 배열의 값들을 합친 값이 음수인지 양수인지에 따라

left와 right 변수의 변경 방향이 결정된다.

 

left는 배열의 가장 왼쪽 인덱스를 (0), right는 배열의 가장 오른쪽 인덱스를 (N-1) 초기값으로 가지므로

temp값이 양수라면 right를 감소시킴으로써 다음 temp 값을 감소시켜야 할 것이며,

temp값이 음수라면 left를 증가시킴으로써 다음 temp 값을 증가시켜야 할 것이다.

 

해당 문제에서는 '서로 다른' 두 수의 합이 0과 가장 가까운 두 수를 구해야 하므로

left와 right가 같아지는 순간 반복문을 종료하게 된다.

 

추가적으로 현재 두 수의 합이 sum보다 0에 가까운지를 판단하는 함수를 작성해야 했는데,

절댓값으로서 판단해야 하기 때문에 sum과 temp가 양수인지, 혹은 음수인지에 따라 조건을 나누어 판단하였다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;
int N;
int arr[100001];

void init();
void input();
bool isNear(int left, int right, int sum);
void solve();

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

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

bool isNear(int left, int right, int sum)
{
    int temp = arr[left] + arr[right];

    if (temp >= 0)
    {
        if (sum >= 0)
        {
            if (sum > temp)
                return true;
            else
                return false;
        }
        else
        {
            if (sum * -1 > temp)
                return true;
            else
                return false;
        }
    }
    else
    {
        if (sum >= 0)
        {
            if (sum > temp * -1)
                return true;
            else
                return false;
        }
        else
        {
            if (sum * -1 > temp * -1)
                return true;
            else
                return false;
        }
    }
}

void solve()
{
    sort(arr, arr + N);

    int left = 0;
    int right = N - 1;
    int sum = 2000000001;

    int r1, r2;

    while (left < right)
    {
        if (isNear(left, right, sum))
        {
            r1 = arr[left];
            r2 = arr[right];

            sum = arr[left] + arr[right];
        }

        if (arr[left] + arr[right] > 0)
        {
            right--;
        }
        else if (arr[left] + arr[right] == 0)
        {
            cout << arr[left] << " " << arr[right];
            return;
        }
        else
        {
            left++;
        }
    }
    cout << r1 << " " << r2;
}

int main()
{
    init();
    input();
    solve();

    return 0;
}