[백준 - 2295] 세 수의 합 .java

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

 

• 입력받은 숫자들 중에 중복을 허용하여 3개를 택하고 그 3개의 합이 입력받은 수들중에 있으면 된다

 

 

3개의 합을 계산하기 위해 3개의 for 문을 중첩해서 사용하면 시간 초과이다

이를 방지하기 위해,

 

• A+B: 숫자 2개의 합을 중복없이 저장해야함 
• T-C: 연산의 결과를 가진 값이 위에서 구한  A+B의 값들중 하나라면 정답 증가
• 두 경우 모두 같은 값이 연달아 올 수 있음을 유의
• 최댓값만 갱신

Set 풀이

A+B한 결과가 중복이 없어야함 -> HashSet 사용

또한 T-C의 결과가 contains()메서드를 활용해서 바로 구할 수 있음

 

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


public class Solution {

    public static void main(String[] args){
    		Scanner sc = new Scanner(System.in);
    		
    		int n = sc.nextInt();
    		int[] nums = new int[n];
    		
    		for(int i =0;i <n;i++) {
    			nums[i] = sc.nextInt();
    		}
    		Arrays.sort(nums);
    		
    		//숫자 두개의 합 조합, 중복 없어야 -> set
    		Set<Integer> sum2 = new HashSet<>();
    		for(int i =0;i<n;i++) {
    			for(int j =0 ;j <n ;j++) {
    				sum2.add(nums[i]+nums[j]);
    			}
    		}
    		
    		int answer = 0;
    		for(int i =0;i<n;i++) {
    			for(int j = 0; j <n;j++) {
    				int t = nums[i] - nums[j];
    				if(sum2.contains(t)) {
    					answer = Math.max(answer, nums[i]);
    				}
    			}

    		}
    		
    		System.out.println(answer);

    	
     }
    
}

 

 

 

이분탐색 - 배열 풀이

 

• A+B 

- 배열의 크기 :  i가 0이면 j는 n번, i가 1이면 j는 n-1번 -> 1부터 n까지의 합 => n(n+1) /2

- 중복 가능 : j의 시작은 i번째부터

- 이분탐색을 위해 오름차순으로 정렬

 

• 이분 탐색 , T-C

- 함수로 구현 : T-C한 값이 sum2 배열에 존재하는지 탐색 

 

 

import java.util.Scanner;
import java.util.Arrays;
public class Main {
	public static boolean isExist(int[] s, int t) {
		int l = 0;
		int r = s.length;
		
		while(l<=r) {
			int mid = (l+r)/2;
			int result = s[mid] - t;
			if(result ==0) return true;
			else if(result>0) r = mid-1;
			else l = mid+1;
		}
		
		return false;
	}
    public static void main(String[] args){
    		Scanner sc = new Scanner(System.in);
    		
    		int n = sc.nextInt();
    		int[] nums = new int[n];
    		
    		for(int i =0;i <n;i++) {
    			nums[i] = sc.nextInt();
    		}
    		
    		Arrays.sort(nums);
    		
    		//두 수의 합, 중복 없어야함
    		int[] sum2= new int[n*(n+1) /2];
    		int index = 0;
    		
    		for(int i = 0; i<n;i++) {
    			for(int j = i; j<n;j++) {
    				sum2[index++] = nums[i] + nums[j];
    			}
    		}
    		
    		
    		Arrays.sort(sum2);
    		
    		int answer = 0;
    		for(int i =0;i<n;i++) {
    			for(int j =0; j<n;j++) {
    				int t = nums[i] - nums[j];
    				if(isExist(sum2,t)) {
    					answer = Math.max(nums[i], answer);
    				}
    			}
    		}
    		System.out.println(answer);


     }
    
}