[JAVA] 백준 2473 세 용액

https://www.acmicpc.net/problem/2473

2473번: 세 용액

- 처음에는 조합이나 백트래킹을 떠올렸는데 5000이라는 범위가 시간초과가 날 것 같았다. 

- 투포인터는 O(N)으로 두 가지를 고를 수 있다는 것을 알고, 한가지 용액과 나머지 두 용액을 고르는 것으로 문제를 해결하였다. 

- 처음에는 투 포인터를 전체 범위에 대해 진행하였지만, i+1 ~ N-1에 대해서만 두 용액을 찾으면 된다는 것을 뒤늦게 깨달았다. 왜냐하면 이미 한 용액을 고르는 순간에 그 한 용액을 포함한 모든 조합을 살펴본 것이고, 이후에는 그 한 용액을 제외하고 조합해도 된다. 

- 입력 범위는 int 범위이기 때문에 int로 값을 받아왔는데, 세 값을 더해주는 연산에서 int 범위가 벗어나 계속 틀렸습니다가 나는 것 같아 입력 배열 타입을 long으로 바꿔서 풀이했다.

- 투 포인터를 연습하기에 좋은 문제였다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        long[] arr = new long[N];
        StringTokenizer st = new StringTokenizer(sc.nextLine());
        for(int i=0;i<N;i++){
            arr[i] = Long.valueOf(st.nextToken());
        }

        Arrays.sort(arr);
        long abs = 3000000000L;
        long[] ans = new long[3];
        for(int i=0;i<N;i++){
            long ch = arr[i];
            int left = i+1;
            int right = N-1;

            while(left<right){
                long val = arr[left] + arr[right] + ch;
                if(Math.abs(val) < abs){
                    abs = Math.abs(val);
                    ans[0] = ch;
                    ans[1] = arr[left];
                    ans[2] = arr[right];
                }
                if(val > 0) right--;
                else if(val<=0) left++;
            }
        }

        System.out.println(ans[0]+" "+ans[1]+" "+ans[2]);
    }
}