[백준] 세 수의 합 2295 - JAVA

문제

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

2295번: 세 수의 합

 

풀이

배열안의 세 수를 더하고 그 값이 배열안에 있는지 확인하는것은 4중 for문을 이용하면 구할 수 있다.

그러나, 문제에서 N이 1000이하이기 때문에 최악을 고려하면 O(n^2) 이나 O(n^2logn)의 시간 복잡도가 나와야 문제가 풀린다.

이 문제는 이진탐색 카테고리에 있는 문제이기 때문에 이진탐색을 이용해야 한다.

a[i] + a[j] + a[k] = a[l] 이라고 할 때 a[i] + a[j]를 구해 리스트로 만든다. 여기서는 N^2의 시간복잡도가 나올것이다. 이를 two 배열(리스트)이라고 하자

two[m] + a[k] = a[l] 이 될 것이고 a[k] - a[l]이 two[m]이 되면 될 것이다. 이부분은 이진 탐색을 이용하면 된다.

 

코드

import java.io.*;
import java.util.*;

class Main{
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		long arr [] = new long [n];
		
		for(int i=0;i<n;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		
		ArrayList<Long> list = new ArrayList<>();
		
		for(int i=0;i<n;i++) {
			for(int j=i;j<n;j++) {
				list.add(arr[i] + arr[j]);
			}
		}
        
		Collections.sort(list);
		
		for(int i=n-1;i>0;i--) {
			for(int j=0;j<i;j++) {
				int idx = Collections.binarySearch(list, arr[i]-arr[j]);
				if(idx >= 0) {
					System.out.print(arr[i]);
					return;
				}
			}
		}
	}
	
}