[백준 2470] 알고리즘 112일차 : 두 용액

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

2470번: 두 용액

C++ 투포인터

음수와 양수가 섞여있는 한 배열에서 두 원소의 합의 절댓값이 최소인 (0에 가까운) 두 원소를 찾는 문제

 

접근방법

처음엔 시간복잡도 때문에 정렬을 쓰면 안될 것 같았는데 퀵소트정렬을 쓰고 N번만 봐도 되면 통과되는 문제였다.

 

우선 오름차순 정렬 후

시작점과 끝점을 양 끝에 두고 시작한다.

두 원소의 합을 비교하면서 포인터를 이동하는건데

이때 두 원소 중 절댓값이 큰 쪽의 포인터를 한칸 안쪽으로 이동한다.

 

왜냐면, 합이 0에 가까워지는게 목표이기 때문에

예를들어 -5, 3 일때 -5를 한칸 안쪽으로 (즉, 0에 더 가까운 쪽으로) 이동시켜야

그나마 0에 가까워질 가능성이 올라가는 것이다.

반대로 -3, 5일때는 양수쪽을 더 작게 해서 0에 가까워져야 하는 것이다.

 

오답노트

합을 저장할 때 절댓값처리를 하지 않은 값을 저장해야

반복문 안에서 마지막에 두 수의 크기 비교가 되는데 이걸 절댓값을 해준 상태로 계속 비교해서 틀렸습니다가 떴었다.

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    //input & init
    int N;
    cin >> N;
    
    int arr[N];
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
    }
    
    long long min;
    int s,e,as,ae;
    
    //process
    sort(arr, arr+N);
    
    as = s = 0;
    ae = e = N-1;
    min = llabs(arr[s]+arr[e]);
        
    long long sum = min;
    while(s < e){
        sum = arr[s]+arr[e];
        if(min > llabs(sum)){
            min = llabs(sum);
            as = s;
            ae = e;
        }
        
        if(sum < 0)
            s++;
        else
            e--;
    }
    
    //output
    cout << arr[as] << " "<< arr[ae] << "\n";
    return 0;
}