[BOJ/C++] 2470 C++

시간 복잡도

• N은 최대 100,000이기 때문에 투 포인터 알고리즘을 사용하면 $O(n)$의 시간 복잡도로 해결할 수 있습니다.

문제 접근법

• 용액의 농도를 입력받은 후 정렬합니다.
• 투 포인터를 이용해 두 농도의 합의 절댓값이 최소가 될 때 두 용액의 농도를 업데이트 합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int N;
    cin >> N;


    vector<int64> v(N);

    for(int i=0; i<N; i++)
        cin >> v[i];
    
    sort(v.begin(), v.end());

    int64 l = 0;
    int64 r = N - 1;

    int64 alkaline = 0;
    int64 acid = 0;

    int64 phMax= INT64_MAX;


    while(l<r)
    {
        int64 ph = v[l] + v[r];

        if(abs(ph) < phMax)
        {
            phMax = abs(ph);
            alkaline = v[l];
            acid = v[r];
        }

        if (ph > 0)
            r--;
        else
            l++;

    }

    cout << alkaline << ' ' << acid;

    return 0;
}