[백준][C++] 2467: 용액

문제

풀이

• 2중 for문을 돌려서 정답을 찾으면 시간 초과가 발생한다. 두 포인터 알고리즘을 이용한다.
• 용액의 입력값이 오름차순으로 입력된다. 용액 vector의 양쪽에서 부터 start와 end로 시작하여 검사한다.
• start가 end의 값을 넘을 때까지 검사하며, start와 end의 합의 절댓값이 현재 answer보다 작다면 갱신한다. 
• start와 end의 합의 부호에 따라 start와 end의 값을 증가하거나 감소시킨다.

코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int N;
    vector<int> v;
    vector<int> answer;

    cin >> N;
    v.resize(N);
    answer.resize(2);

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

    int start = 0;
    int end = N - 1;
    answer[0] = v[start];
    answer[1] = v[end];

    // vector의 양쪽에서 다가오면서 start가 end를 넘어설 때 까지 검사
    while (start < end)
    {
        // 현재 start와 end의 합의 절댓값이 answer의 절댓값보다 작다면 갱신
        if (abs(answer[0] + answer[1]) > abs(v[start] + v[end]))
        {
            answer[0] = v[start];
            answer[1] = v[end];
        }

        // 합이 0보다 작다면 음수의 절댓값이 크므로 start를 1증가
        if (v[start] + v[end] < 0)
        {
            start++;
        }
        else
        {
            end--;
        }
    }

    cout << answer[0] << " " << answer[1];

    return 0;
}