[백준] 2473: 세 용액 JAVA

접근

알고리즘 분류를 봤더니 두 포인터 말고도 이분탐색이 함께 있는걸 알게됐다. 두 방법 모두로 풀 수 있으며, 시간 효율은 이분탐색이 O(N^2logN), 투포인터가 O(N^2)로 투포인터 방식이 더 효율적이다. 투포인터의 경우에는 하나의 용액을 고정한 뒤 나머지 두 용액의 값을 투포인터로 찾는 방식이고, 이분탐색의 경우에는 두 개의 용액을 고정한 뒤 나머지 하나의 값을 이분탐색으로 찾는 방식이다. 이 문제에서 주의할 점은, 세 용액을 합했을 때 그 값이 최대 1,000,000,000 * 3으로 int의 범위를 넘어갈 수도 있다는 점이다. 따라서 최소가 되는 절댓값을 비교할 때 int가 아니라 long에 저장을 해야 한다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static long MAX_VALUE = (long)1000000000 * 3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] answer = new int[3];

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

        // 투 포인터 적용
        long minSum = MAX_VALUE;

        for (int i = 0; i < n-2; i++) {
            int left = i + 1, right = n-1;

            while(left < right) {
                long sum = (long)arr[i] + arr[left] + arr[right];

                if (Math.abs(sum) < minSum) {
                    minSum = Math.abs(sum);
                    answer[0] = arr[i];
                    answer[1] = arr[left];
                    answer[2] = arr[right];
                }

                if(sum == 0) break;
                else if (sum < 0) left++;
                else right--;
            }
        }

        for (int i = 0; i < 3; i++)
            System.out.print(answer[i] + " ");
    }
}