백준 2470 - 두 용액 (C++)

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

2470번: 두 용액

 

풀이 

이분탐색과 투포인터 문제이다.

벡터의 첫 원소를 시작으로 기준 원소를 정한다. 그 후, 그 외의 원소들을 이분탐색한다.

각 원소들과 기준 원소의 차이를 비교하며 가장 차이가 적은 원소 2개를 찾는다.

 

주의할 점! 용액 하나가 10억의 값을 가질 수 있으므로 넘을 수 있으므로 최소값에 넣어 둔 값을 20억 정도로 해줘야 함.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<int> v;
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());

    int minVal = 2147483647;
    int idx = 0;
    int min1, min2;

    while (idx < N - 1) {
        int low = idx + 1, high = N - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (v[mid] + v[idx] == 0) {
                minVal = 0;
                min1 = v[idx];
                min2 = v[mid];
                break;
            } else if (v[mid] + v[idx] < 0) {
                if (abs(v[mid] + v[idx]) < minVal) {
                    minVal = abs(v[mid] + v[idx]);
                    min1 = v[idx];
                    min2 = v[mid];
                }
                low = mid + 1;
            } else {
                if (abs(v[mid] + v[idx]) < minVal) {
                    minVal = abs(v[mid] + v[idx]);
                    min1 = v[idx];
                    min2 = v[mid];
                }
                high = mid - 1;
            }
        }
        idx++;
    }
    cout << min1 << " " << min2;
}