세 수의 합

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

 

유형

• 해시
• 이분 탐색

 

풀이방법

int 배열에서 x + y + z = k가 존재할 때, k의 최대값을 찾는 문제다. (단, 인덱스는 중복 가능)

 

1. 배열을 이중 탐색하며 x + y합을 HashSet에 저장한다. 이 때 배열의 마지막 값은 저장하지 않아도 된다. (정렬이 된 경우에)
2. x + y를 이제 알았으니 k - z를 배열을 순회하며 확인한다. 배열을 이중으로 순회하며 arr[i] - arr[j]를 하게되면 모든 k - z의 순서쌍을 구할 수 있다. 이 때, 해당 값이 set에 존재한다면 k의 최댓값을 갱신해준다. (arr[i]를 통해)

 

이분 탐색을 통해서도 값을 탐색할 수 있는데 HashSet이 더 로직을 구현하기 편했던것 같다. 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class boj2295 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int [] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // A + B + C = K일 때 K의 최댓값을 구하는 문제

        // 1. 모든 A+B 경우의 수를 HashSet에 저장 (이 때 인덱스는 같아도 된다.

        Set<Integer> set = new HashSet<>();
        Arrays.sort(arr);

        for(int i = 0; i < n - 1; i++) { // 마지막 값까진 구할 필요 없음
            for(int j = 0; j < n - 1; j++) {
                set.add(arr[i] + arr[j]);
            }
        }

        // 2. A+B = K-C를 구해야 한다. 배열을 다시 순회하며 뺀 모든 경우의 수를 찾는다.

        int max = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int diff = arr[i] - arr[j];
                if (set.contains(diff)) { //
                    // 3. 이 때 값이 존재한다면 K값의 최댓값을 갱신해주면 됨
                    max = Math.max(max, arr[i]);
                }
            }
        }
        System.out.println(max);
    }
}