[BOJ] 2467번 : 용액(C++)

문제 링크 : 백준 2467번

[문제 접근]

하나 하나씩 탐색하면 n<=100,000 이므로 시간초과가 발생하게 된다.
따라서 나는 투 포인터를 이용해 접근했다.
(문제에서 이미 정렬해서 주기 때문에 따로 정렬할 필요는 없다)

1. 양 끝 점에 포인터를 만들어준다.(start와 end)
2. start와 end의 값을 더해서 절대값을 씌워준다.
3. 절대값을 씌운 값이 ans보다 작을 경우 갱신해주고 (0에 더 가까우므로) 정답에 값을 대입해준다.
4. 절대값을 씌우지 않은 값이 0보다 크면 음수값이 더 커야 0에 가까워지므로 end를 1 감소시준다.
5. 반대로 0보다 작으면 양수값이 더 커야 0에 가까워지므로 start를 1 증가시켜준다. (0과 같을 때는 정답이므로 크게 상관하지 않아도 된다.)

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n;
int arr[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        cin >> arr[i];
    }

    int ans = 2000000001;

    int start = 1, end = n;
    int first, second;
    while(start<end) {
        int now = arr[start] + arr[end];
        int num = abs(now);
        if(ans>num) {
            ans = num;
            first = arr[start], second = arr[end];
        }
        if(now>0) end--;
        else start++;
    }
    cout << first << " " << second;
    return 0;
}