[Java] 백준 2473번 세 용액

투포인터 문제입니다.

세개의 숫자를 골라서 합의 절대값이 0과 가장 가까운 값들을 찾아야합니다.
두개의 숫자를 고르는 (용액, 두 용액) 문제와 유사합니다.

N이 5000이므로 O(N^2)으로 처리할 수 있습니다.
0~N까지 고정점을 두고 나머지 두개의 수를 투포인터로 이동하면서 0과 가까운 수를 찾아주었습니다.

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    long goodSum = Long.MAX_VALUE;
    int goodI = 0;
    int goodLeft = 0;
    int goodRight = 0;

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(arr);

    for (int i = 0; i < n - 2; ++i) {
      int left = i + 1;
      int right = n - 1;
      while (left < right) {
        long sum = arr[left] + arr[right];
        long sum2 = Math.abs(arr[i] + sum);
        if (goodSum > sum2) {
          goodSum = sum2;
          goodI = i;
          goodLeft = left;
          goodRight = right;
        }

        if (arr[i] + sum > 0) {
          --right;
        } else {
          ++left;
        }
      }
    }

    bw.write(arr[goodI] + " " + arr[goodLeft] + " " + arr[goodRight] + "\n");
    bw.close();
  }
}