[백준] 2295번 세 수의 합(java)

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

2295번: 세 수의 합

핵심

x + y + z = k 가 돼야 한다. 각각의 원소는 집합에 포함되어 있다. 또한 각각은 같은 값을 가져도 된다.

단순하게 완전탐색으로 풀면 시간복잡도에서 걸리게 된다. (3중 for문)

따라서 이분탐색을 사용하여 더 빠르게 풀 수 있다.

x + y = k -z라는 식을 이용하면 된다.

 

 

정답 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++)arr[i] = sc.nextInt();
        List<Integer> sum = new ArrayList<>();
        for (int i = 0 ; i < N ; i++){
            for (int j = 0 ; j < N; j++){
                sum.add(arr[i] + arr[j]);
            }
        }
        Arrays.sort(arr);
        Collections.sort(sum);

        for (int i = N-1; i>=0; i--){
            for (int j = N-1; j>=0; j--){
                int minus = arr[i] - arr[j];

                if (Collections.binarySearch(sum,minus)>=0){
                    System.out.println(arr[i]);
                    return;
                }
            }
        }
    }
}

해설

List에 x+y의 값들을 넣어준다. 이제 2개의 값을 뺀 값이 List에 담겨있다면, 그 수는 정답가능성이 있다.

x + y = k - z 라면, 가장 큰 k값을 찾아야 하므로, minus를 구할 때 N-1부터 시작하게 된다.

중요한 점은 뺀 값이 sum에 포함여부를 확인할 때 단순하게 contain을 사용하면 O(n)이 걸리게 된다.

따라서 binarySearch를 사용하여 시간을 단축해야 한다.

 

 

배운 점

첫 시도는 완전 탐색을 사용하여 시간복잡도에서 걸리게 되었다.

이후 contain을 사용하여 포함여부를 확인하였는데, 이때도 동일하게 시간복잡도에서 걸리게 되었다.

정렬이 된 상태라면 binarySearch를 사용하는 게 매우 이득이기 때문에 이러한 습관을 사용하자.

또한 Collection의 경우 이미 binarySearch가 구현되어 있으므로 메서드를 사용하자.