[BOJ] 2467 - 용액

정렬된 배열 중 두 값을 더해 0에 가장 가까운 두 값을 찾는 문제이다.

문제풀이 전략

풀이 1
처음 이 문제를 풀 때는 투포인터를 사용하였다.

시작점과 끝점을 정한 후 두 값을 더한 것이 0보다 크면 끝점을 줄이고, 0보다 작으면 시작점을 증가시킨다.

이 방법을 사용하면 O(n)이면 충분히 풀이가 가능하다.

풀이 2
다른 풀이로는 이분탐색을 사용할 수 있다.

0과 가장 가까운 값을 찾는 문제이기에 현재 값을 음수로 바꾼 값과 가장 가까운 값을 찾으면 된다.

예를들어 현재 탐색하는 값이 8 일 경우 0과 가장 가까워 지기 위해서는 -8과 가장 가까운 값이어야 한다.

그래서 현재 탐색하는 값을 음수로 바꾼 값을 주어진 배열 안에서 찾아내면 된다.

이 과정을 배열의 첫 값부터 끝 값까지 반복하면 된다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

int n;
vector<int> v;
int target = 2000000000;
void f1_tp(){
    int s = 0;
    int e = v.size()-1;
    int ans[2] = {-1,-1};

    while(s < e){
        int sum = v[s] + v[e];
        if(abs(sum) < target){
            ans[0] = v[s];
            ans[1] = v[e];
            target = abs(sum);
        }
        if(sum >= 0){
            e--;
        }else{
            s++;
        }
    }
    cout << ans[0] << " " << ans[1] << "\n";
}

void f2_bs(){
    int ans[2] = {-1,-1};
    for(int i=0;i<v.size();i++){
        int idx = lower_bound(v.begin(), v.end(), -v[i]) - v.begin();
        for(int j = idx-1;j<=idx;j++){ // idx-1 vs idx
            if(j == i || j<0 || j>=n)
                continue;
            if(v[j] + v[i] == 0){
                ans[0] = v[j];
                ans[1] = v[i];
                if(ans[0] > ans[1])
                    swap(ans[0], ans[1]);
                cout << ans[0] << " " << ans[1] << "\n";
                return;
            }else{
                if(target <= abs(v[j] + v[i]))
                    continue;
                ans[0] = v[j];
                ans[1] = v[i];
                target = abs(v[j] + v[i]);
            }
        }
    }
    if(ans[0] > ans[1])
        swap(ans[0], ans[1]);
    cout << ans[0] << " " << ans[1] << "\n";
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }

    //f1_tp(); // two pointer
    f2_bs(); // binary search
}

출처
https://www.acmicpc.net/problem/2467