[백준] 용액

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

2467번: 용액

우선 문제부터 간단하게 요약하면, 

 

-1,000,000,000 ~ 1,000,000,000 의 범위를 가지는 숫자들이 정렬되어 구성된 순열이 주어지면, 해당 순열의 두 수를 더해서 0과 가장 가까운 경우가 되는 경우를 출력해야 하는 문제입니다.

 

<Solution>

투포인터 알고리즘을 이용하여, 만약 현재 양쪽의 값을 더했을 때, 양수라면 right pointer --, 음수라면 left pointer ++ 을 함으로 써 문제를 해결할 수 있습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>

using namespace std;

int numArray[100000+10];
int N;

int abs(int a, int b){
    return (a-b >= 0) ? a-b : -1*(a-b);
}

int main(){
    cin >> N;
    for(int i = 0; i<N; i++){
        cin >> numArray[i];
    }

    // search with two pointer algorithm
    int leftPtr = 0;
    int rightPtr = N-1;
    int closeVal = 2000000001;

    int solution1, solution2;

    while(rightPtr> leftPtr){
        int k = numArray[rightPtr] + numArray[leftPtr];
        if(abs(k) < closeVal){
            closeVal = abs(k);
            solution1 = numArray[leftPtr]; solution2 = numArray[rightPtr];
        }

        if(k < 0) leftPtr++;
        else if(k > 0) rightPtr--;
        else{
            k = 0; break;
        }

    }

    cout << solution1 << ' ' << solution2 << endl;
}