[Baekjoon] 2295 세 수의 합 (Java)

문제 링크

백준2295-세 수의 합

문제

문제가 간단하다. N개의 자연수 집합에서 3개의 수를 뽑아 합한 값이 집합에 존재하는지 확인하고, 그 최댓값을 출력하는 문제이다.

풀이

처음 봤을 때 풀이법은 한 가지라고 생각했다. 3가지 수를 확인하기 위해서는 불가피하게 3중 반복문을 통해 수를 뽑아야 하고, 해당 값이 존재하는지 확인은 이분탐색을 통해 최적화하는 N^3logN 풀이가 유일하다고 생각했다. 그래서 삽질을 더 많이 했다.

이 문제는 N^2logN 안에 해결해야 한다. 여기서 아이디어가 필요하다.
먼저 집합에서 2개의 수를 뽑아 새로운 집합 two를 구성한다. 이후 O(N^2)으로 기존 집합을 확인하면서 nums[i]-nums[j]의 값이 two에 존재하는 지 확인한다. 만약 존재한다면 nums[i]와 nums[j]중 큰 수가 세 수의 합이 된다.

a+b+c = d 를 찾는다고 했을 때 a,b,c를 선택하려면 3중 반복문이 필요하다고 생각했다. 하지만 식을 변형하여 a + b = d - c 로 봤을 때 양쪽 식 각각의 수를 결정하는 건 N^2안에 해결가능하고, target값을 찾는 과정에서 이분탐색을 활용하면 logN이 곱해진다.
N^2 + N^2logN = O(N^2logN)
이런식으로 시간복잡도를 줄일 수 있다는 것을 배웠다.

코드

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

public class Main{

    private static int N;
    private static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        List<Integer> nums = new ArrayList<>();
        List<Integer> two = new ArrayList<>();

        for(int i=0; i<N; i++){
            int num = Integer.parseInt(br.readLine());
            nums.add(num);
        }

        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                two.add(nums.get(i)+nums.get(j));
            }
        }
        Collections.sort(two);
        
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                int target = nums.get(i)-nums.get(j);
                int idx = Collections.binarySearch(two,target);
                if(idx>=0){
                    answer = Integer.max(answer, Integer.max(nums.get(i),nums.get(j)));
                }
            }
        }
        System.out.println(answer);
    }
}