[2470] 두 용액

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

2470번: 두 용액

배열에서 a[i]+a[j]가 0에 가장 가까우며 서로다른 i와 j를 찾는 문제이다.

그외의 조건은 N=100000, -10억<=a[i]<=10억

문제의 조건이 살짝 강화되어 a[i]가 최대 20억정도로 올라간다면, a[i]+a[j]>MAX_INT인 경우가 존재해

순간적으로 오버플로우가 발생할 수 있지만, 이 문제는  -20억<=a[i]+a[j]<=20억인 관계로

int형으로도 충분히 커버가 된다.

 

완전탐색이 O(N^2)이고, 이보다 더 효율적인 알고리즘을 사용해야 하는데,

사용할 수 있는 알고리즘은 크게 두개로 아래와 같다.

1.이분 탐색

2.투포인터

어느쪽이든 사전정렬이 필요해 시간복잡도는 O(NlogN)이 나온다.

이분탐색에서 a[i]를 임의로 지정해

브루트포스와 이분탐색을 조합하듯 구현할 경우(모든 a[i]에 대해 최선의 a[j]를 찾는경우)

O(logN)의 탐색을 a[0]~a[n-1] ->n번 반복하므로 탐색에 총 O(NlogN)의 시간이 소요된다.

반면에 투포인터를 사용하면 탐색에 O(N)의 시간만 소요되므로 전체적인 시간복잡도는 아래와 같다.

 

브루트포스+이분탐색 : O(NlogN)+O(NlogN)

투포인터 : O(NlogN)+O(N)

 

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int INF = 2121212121;
int n;
vector<int>a;
int main(void) {
    int i, j;
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a.begin(), a.end());
    int ans_score = INF, ans_i = 0, ans_j = 0;
    for (i = 0; i < n; i++) {
        int cur = a[i];
        int idx = lower_bound(a.begin(), a.end(), -cur) - a.begin();
        for (j = idx - 1; j <= idx; j++) {
            if (j < 0 || j >= n || i == j)continue;
            int score = abs(a[i] + a[j]);
            if (score < ans_score) {
                ans_score = score;
                ans_i = i;
                ans_j = j;
            }
        }
    }
    if (ans_i > ans_j)swap(ans_i, ans_j);
    printf("%d %d", a[ans_i], a[ans_j]);
    return 0;
}

-a[i]에 대한 lower_bound의 인덱스를 idx에 저장한 다음 idx와 함께 idx-1도 함께 확인해야한다.

a[idx~MAX]까지의 값은 항상 -a[i] 이상이기에

a[idx]와의 score와 같거나 더 크지만(우선순위가 같거나 낮아 갱신이 필요없지만)

idx 이전의 값은 갱신이 필요하다. 그 반례로 아래와 같은 경우를 생각해보자.

input : {-3, 1, 100}

cur==-3일때 idx는 2이다 -> score : 97

cur==1일때 idx는 1이다 -> 갱신 없음(i==j)

cur==100일때 idx는 0이다 ->score : 97

output : 97(?)

 

이 문제의 정답은 -3+1 = 2가 되어야한다.

lower_bound는 target '이상'의 값이 '처음으로' 나오는 반복자를 반환하는데

target과 완전히 같은 값이 존재하다면(두개를 합쳐 0을 만들 수 있으므로) 관계없지만

abs(cur-a[idx])>abs(cur-a[idx-1]) 인 경우가 반례로 남는다.

 

또한, idx-2를 탐색하지 않는 이유는 idx+1, idx+2, idx+3...을 탐색하지 않는 이유와 동일하다.