BOJ2295 세 수의 합

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

2295번: 세 수의 합

이진탐색이 아닌 SET 자료형으로도 풀 수 있다. 합을 set에 저장해두고 contains로 확인하는 방법이다. 로직은 똑같다.

contains는 O(1)이다.

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		int[] num = new int[n];
		for(int i=0;i<n;i++){
		    num[i]=Integer.valueOf(br.readLine());
		}
		
		Arrays.sort(num);
		
		int[] num2= new int[n*(n+1)/2];
		//num2는 원소 2개의 합으로 나올 수 있는 수의 집합 N^2
		
		
		int index =0;
		for(int i=0;i<n;i++){
		    for(int j=i; j<n;j++){
		        num2[index++] = num[i]+num[j];
		    }
		}
		
	    Arrays.sort(num2);
		
		// num1의 최대값부터 낮은수로 내려가면서 N
		// num에서 하나 고르고 num2에서 이진탐색으로 해당 값이 있는지 체크 N * 2logN
		// 총 N*N*logN

		
		for(int i=n-1;i>=0;i--){
		    for(int j=0; j<n;j++){
		        int goal = num[i];
		        if(Arrays.binarySearch(num2,goal-num[j])>=0){
		            System.out.println(goal);
		            return;
		        }
		    }
		}
		
		
		
	}
}

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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();

        Set<Integer> sums = new HashSet<>();
        for (int i = 0; i < N; i++)
            for (int j = i; j < N; j++)
                sums.add(arr[i] + arr[j]);

        int ans = -1;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                int target = arr[i] - arr[j];
                if (sums.contains(target))
                    ans = Math.max(ans, arr[i]);
            }
        System.out.println(ans);
    }
}