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

 

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

 

배열의 주어진 값들 중 두 값을 선택해서 더한 결과 중 0에 가까운 두 수를 찾는 문제다

 

투 포인터, 이분탐색으로도 해결 가능하지면 정렬을 이용해서 해결했다.

 

compare 함수를 구현하면 정렬기준을 직접 정의할 수 있는데 더한 결과 중 0에 가깝다는건 연속된 두 값의 차이가 가장 작아야 하므로 compare함수를 아래처럼 구현해주면 절대값을 한 수들이 0과 가까운 수 기준으로 정렬된다

bool compare(int a, int b) {
    return abs(a) - abs(b) > 0;
}

 

아래 케이스는 코드를 짜면서 만든 케이스인데

정렬 전
10
-10 -8 -2 0 1 2 5 13 14 17

정렬 후
0 1 -2 2 5 -8 -10 13 14 17

위 compare로 정렬하고 나서 v[i]와 v[i + 1]을 비교해서 diff값을 갱신하면 된다.

시간복잡도는 정렬에 O(logN), 비교에 O(N)이므로 O(logN + N)정도가 된다.

 

덤으로 2467번 용액 문제도 코드를 그대로 내면 맞는다(https://www.acmicpc.net/problem/2467)

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
bool compare(int a, int b) {
    return abs(a) - abs(b) < 0;
}
int main() {
    FASTIO
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0; i < n; i++) {
        int k; cin >> k;
        v.push_back(k);
    }
    sort(v.begin(), v.end(), compare);
    int mn = 0, mx = 0, diff = 2000000001;
    for(int i = 0; i < n - 1; i++) {
        if(diff > abs(v[i] + v[i + 1])) {
            diff = abs(v[i] + v[i + 1]);
            mn = v[i];
            mx = v[i + 1];
            if(diff == 0) {
                break;
            }
        }
    }
    if(mn > mx) {
        swap(mn, mx);
    }
    cout << mn << ' ' << mx;
}