[백준] 2295번 - 세 수의 합 [Java]

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

 

[백준] 2295번 - 세 수의 합 [Java]

[백준] 2295번 - 세 수의 합 [Java]

---

1.  아이디어

 

x + y + z = k 를 x + y = k - z 로 생각하면 O(N^3) 보다 빠르게 해결할 수 있다.

---

2. 문제풀이

 

N이 최대 1000이어서 3중 for문을 이용한 단순한 풀이로는 해결할 수 없다.

아이디어처럼 두 수의 합들을 먼저 구한 후 두 수의 차가 두 수의 합에 포함될 경우 k를 구할 수 있다.

 

구현에서는 입력을 배열로 받아서 정렬한 후 두 수의 합은 HashSet에 저장했다. 이후 2중 for문을 역방향 순회하며 두 수의 차가 HashSet에 포함될 경우 z에 해당하는 값을 더하는 방식으로 구현했다. 배열을 정렬했어서 처음 찾는 값이 최대가 된다.

---

3. 코드

 

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

public class Main {
    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());
        }
        Arrays.sort(arr);

        Set<Integer> set = new HashSet<>();
        for (int x = 0; x < N; x++) {
            for (int y = x; y < N; y++) {
                set.add(arr[x] + arr[y]);
            }
        }

        int ans = 0;

        out:
        for (int k = N - 1; k >= 0; k--) {
            for (int z = k; z >= 0; z--) {
                int diff = arr[k] - arr[z];

                if (set.contains(diff)) {
                    ans = diff + arr[z];
                    break out;
                }
            }
        }

        System.out.println(ans);
    }
}

---

4. 후기