[백준] 2295번 : 세 수의 합

문제

 

접근 방식

주어진 수들에서 중복을 허용하여 3개의 수를 더한 값이

이미 배열에 존재하는 경우 중 가장 큰 값을 찾아야 한다.

 

수들이 최대 1000개 주어지기 때문에 3중 반복문으로

모든 경우를 다 곱하는 경우만 해도 최대 10억 번의 계산이 필요해

값을 찾기까지 하려면 절대 불가능한 방법이다.

 

문제를 x + y + z가 아니라 (x + y) + z로 나누어 생각해보면

x + y를 먼저 구해둔 후에 합해서 z가 될 수 있는 경우를 찾으면 된다.

 

x + y를 모두 구하면 최대 1,000,000개가 나올 수 있기 때문에

이걸 매번 O(N)으로 반복 순회하면 안되고

정렬하여 이분 탐색으로 찾아주면 된다.

 

정리하면 아래와 같다.

1. 배열을 정렬한다. nums

2. (x + y) 쌍을 구한다. pairs

3. 구한 쌍들도 정렬한다. 

4. 큰 값부터 찾기 위해 기존 배열을 역순으로 순회하며

5. 기존 배열을 원래대로 순회하면서 값을 빼주고 그 값이 구한 쌍에 존재하는지 확인한다.

(pairs에 nums[i] - nums[j]가 존재하는지)

 

풀이

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[] nums = new int[n];
		List<Integer> pairs = new ArrayList<>();

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

		Arrays.sort(nums);

		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				pairs.add(nums[i] + nums[j]);
			}
		}

		Collections.sort(pairs);
		int idx = -1;

		out:
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < n; j++) {
				if (Collections.binarySearch(pairs, nums[i] - nums[j]) >= 0) {
					idx = i;
					break out;
				}
			}
		}

		System.out.println(nums[idx]);
	}
}