[백준] 2295. 세 수의 합

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

2295번: 세 수의 합

• a + b + c = d에서 가장 큰 d의 값을 찾는 문제이다. 
• 주 포인트는 a + b = d - c로 생각해야 한다.
• 즉, 이중 반복문으로 a + b의 모음들을 만들고, 이분 탐색으로 d - c가 a + b 모음들에 포함되나 확인하면 된다.
• 그런데 이때 d - c의 값이 a + b의 모음에 포함되나 확인할 때, ArrayList.contain() 메소드를 사용하면 시간초과가 뜬다. 찾아보니 ArrayList.contain() 메소드는 O(N)의 시간 복잡도를 갖는다고 한다. 즉, 전체 시간 복잡도가 O(N^3)가 되기 때문에 시간초과가 뜨는 것이다.
• 따라서 이분 탐색을 통해 O(logN)의 시간이 소요되도록 하며, 전체 시간 복잡도는 O(N^2 * logN)이 된다.
• 참고로 직접 이분 탐색을 구현하지 않고 Collections.binarySearch() 메소드를 사용해도 된다. 이 메소드는 정렬된 리스트에서 매개변수로 받은 객체의 위치를 찾아서 index를 반환하는데, 객체가 없으면 -1을 반환한다.

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

// 시간 복잡도 = O(N^2 * logN)
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static int[] arr;
    static List<Integer> list = new ArrayList<>();
    static int answer = 0;

    public static void main(String[] args) throws IOException {

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

        // 이중 반복문으로 a + b의 집합 만들기
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                list.add(arr[i] + arr[j]);
            }
        }
        Collections.sort(list);

        // 이분 탐색으로 x - c를 찾고, a + b 집합에 있는지 확인하기
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
//                Collections.binarySearch() 메소드를 사용하는 경우
//                if (Collections.binarySearch(list, arr[j] - arr[i]) >= 0) {
//                    answer = Math.max(answer, arr[j]);
//                }
                binarySearch(arr[j], arr[i]);
            }
        }

        System.out.println(answer);
    }

    private static void binarySearch(int max, int min) {
        int diff = max - min;
        int start = 0;
        int end = list.size() - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            // 있는 경우
            if (list.get(mid) == diff) {
                answer = Math.max(answer, max);
                return;
            }
            if (list.get(mid) > diff) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }
}