문제 출처

1. 문제설명

  • N개의 수열이 주어진다.
  • 수열에서 3개의 수를 뽑아 0에 가장 가까운 세 개의 수를 구하라



2. 알고리즘 설계

  • 이전 문제와 달리, 0인 경우가 있다고 단정할 수 없다.
    • lower, upper_bound 사용 불가
  • 투 포인터 방식으로 접근해야 한다.
  • 로직
    • for loop를 i-2번째까지 실행한다.
      • 3개의 수를 추첨해야 하기 때문
    • left=i+1, right=n-1로 설정
    • 매순간 arr[i] + arr[left] + arr[right]가 좀 더 0에 가까운 수인지 체크
    • 값이 0보다 작다면 left++, 그 외의 경우 right--



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1000000005;
ll n, arr[5005];
vector<ll> ans;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ans = {INF, INF, INF};

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> arr[i];

    sort(arr, arr+n);

    for(int i=0; i<n-2; i++) {
        int left=i+1, right=n-1;
        while(left < right) {
            ll cmp = arr[i] + arr[left] + arr[right];
            if(abs(ans[0]+ans[1]+ans[2]) > abs(cmp))
                ans = {arr[i], arr[left], arr[right]};
        
            (cmp < 0) ? left++ : right--;
        }
    }

    for(ll a : ans) cout << a << ' ';

    return 0;
}



4. 소감

  • arr의 값 세 개를 더할 때, 최대/최소 값이 +-10억이므로, int overflow가 발생할 수 있다.
  • 그냥 전부 long long으로 선언해버리자