[백준] 2473번 : 세 용액

🤔 문제분석

📝 문제요약

3개이상의 용액이 주어졌을때 3개를 뽑아서 합이 0에 가장 가까운 용액을 찾는 문제이다.

🎯 필요한 개념

• 투포인터

✅ 알고리즘

1. 용액을 오름차순으로 정렬한다.
2. 2중 for문으로 2가지의 용액을 뽑는다.
   1. 남은 하나의 용액을 투포인터를 활용하여 찾는다.
      1. 합이 0보다 작은경우 Left를 증가 시킨다.
      2. 합이 0보다 큰경우 Right를 증가 시킨다.
3. 모든 경우를 탐색하면서 가장 0에 가까운 용액을 찾아서 오름차순 정렬하여 리턴한다.

💻 코드

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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    sort(A.begin(), A.end());

    long long closestSum = 9876543219876543321;
    vector<long long> answer(3);

    for (int i = 0; i < N-2; i++) {
        int left = i + 1, right = N - 1;
        while (left < right) {
            long long sum = A[i] + A[left] + A[right];
            if (abs(sum) < abs(closestSum)) {
                closestSum = sum;
                answer = {A[i], A[left], A[right]};
            }
            if (sum > 0) right--;
            else if (sum < 0) left++;
            else break; // sum이 0인 경우 최적 해를 찾음
        }
        if (closestSum == 0) break; // 최적 해를 찾으면 더 이상 탐색 중지
    }

    sort(answer.begin(), answer.end());
    for (long long v : answer) cout << v << ' ';
    cout << '\\n';

    return 0;
}