[백준] 세 용액 Java

세 용액

두 용액에서 하나 늘린 문제입니다.

for문으로 하나씩 고정값을 지정해주고 두 용액찾기를 하면 O(n^2)로 찾을 수 있습니다.

단 left 인덱스를 for문의 index보다 크게 해줘야 41퍼 틀림을 넘길 수 있습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        long[] arr = new long[N];

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


        long gap = Long.MAX_VALUE;
        long[] rsl = new long[3];
        int target = 0;
        long sum;
        long tmp;

        for(int i = 0; i < N; i++){
            int right = N-1;
            int left = i+1;
            long fixed = arr[i];
            while (left < right) {
                sum = arr[right] + arr[left] + fixed;
                tmp = Math.abs(sum);
                if (tmp < gap) {
                    gap = tmp;
                    rsl[0] = fixed;
                    rsl[1] = arr[left];
                    rsl[2] = arr[right];
                }

                if (sum > target) right--;
                else left++;
            }
        }

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