코드

잘못된 것

순차 탐색으로 o(n^2) 으로 시간 초과 가 난다.

#include <iostream>
#include <cmath>
using namespace std;
int a[1000001];
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int maxsum = a[0] + a[1];
    int select1 = 0;
    int select2 = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int sum = a[i] + a[j];
            if (abs(sum - 0) < abs(maxsum))
            {
                select1 = i;
                select2 = j;
                maxsum = sum;
            }
        }
    }

    cout << a[select1] << " " << a[select2];
    return 0;
}

잘 한것

이분탐색으로 시간 복잡도가 O(nlogn) 이다.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long a[1000001];
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    /*for (int i = 0; i < n; i++)
    {
        cout << a[i];
    }*/
    int start = 0;
    int end = n - 1;
    long long maxsum = 9876543210;
    int select1 = 0;
    int select2 = n - 1;
    while (start < end)
    {
        long long sum = a[start] + a[end];
        if (abs(sum) < abs(maxsum))
        {
            select1 = start;
            select2 = end;
            maxsum = sum;
        }
        if (sum < 0)
            start++;
        else
            end--;
    }
    cout << a[select1] << " " << a[select2];
    return 0;
}

해결 방법

1. 정렬함 (시간 복잡도 o(nlogn))
2. sum = 두개 선택한 것
   만약 sum 이 음수라면, start 를 늘려줌. 양수로 가는 방향
   sum 이 양수라면, end 를 줄여줌, 음수로 가는 방향.