백준 2295 세 수의 합 (JAVA 자바 풀이)

백준 2295 세 수의 합 (JAVA 자바 풀이)

 

---

 

 

 

---

문제의 요구사항을 그대로 구현하여 모든 경우의 수를 탐색하는 방식은 다음과 같을 것이다. 

 

for (int i =0; i< N; i++){
  for (int j =0; j<N; j++) {
     for (int k =0; k<N; k++) {
       int sum = arr[i] + arr[j] + arr[k];
       if (set.contains(sum)) {
         answer = Math.max(answer, sum)
       }
    }
 }

 

숫자의 개수가 최대 1,000개 이므로 O(n^3)의 시간복잡도로 풀이할 수 없다. 

 

 

두 수의 합이라고 생각해보자. 

 

마찬가지로 반복문을 2번 그대로 돌리면 O(n^2)이 될 것이다.

 

그러나 

어떤 두 수 A + B = X가 된다는 것은 다른 수식으로 쓰면 A = X - B로 표현할 수 있다.

즉, A에 대해 X - B가 존재하는가? 에 대한 질문으로 바뀐다. 

 

배열의 인덱스에 해당 값을 기록하였다면 

arr[value] 를 통해 상수 시간 내에 해당 값을 찾을 수 있어 O(n^2)의 시간 복잡도를 O(n)으로 낮출 수 있다. 

 

세 수의 합도 이와 같은 원리를 이용해보자. 

 

A + B + C = X 즉 세 수의 합이 전체 집합에 있는가에 대한 질문은 

A + B = X - C로 바꾸어 쓰면 

X - C 가 A + B의 집합에 있는가에 대한 질문으로 바뀐다. 

 

이 경우 2차원 배열을 한 번 돌려 A+B의 집합을 구할 수 있고 

나머지 두 수 X, C에 대해 모든 경우를 탐색하면서 각각에 대해 

이분 탐색으로 배열에서 존재하는지를 탐색하면 

O(n^2) * O(logn) 의 시간 복잡도를 갖게 된다. 

 

 

 

1) A + B 집합을 구하고 정렬하기 

int[] twoValuesSum = new int[(numbers.length * (numbers.length + 1)) / 2];
int count = 0;
for (int i = 0; i < numbers.length; i++) {
   for (int j = i; j < numbers.length; j++) {
      twoValuesSum[count++] = numbers[i] + numbers[j];
   }
}
Arrays.sort(twoValuesSum);

=> 시간 복잡도 O(n^2) + O(nlogn) => O(n^2)

 

 

2) X - C를 탐색하기 

int answer = -1;
for (int i = 0; i < numbers.length; i++) {
   for (int j = 0; j < numbers.length; j++) {
      if (binarySearch(twoValuesSum, numbers[i] - numbers[j])) {
         answer = Math.max(answer, numbers[i]);
      }
   }
}

=> 시간 복잡도 O(n^2 * nlogn) 

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int N = Integer.parseInt(stringTokenizer.nextToken());
		int[] numbers = new int[N];
		while (N-- > 0) {
			numbers[N] = Integer.parseInt(bufferedReader.readLine());
		}


		int[] twoValuesSum = new int[(numbers.length * (numbers.length + 1)) / 2];
		int count = 0;
		for (int i = 0; i < numbers.length; i++) {
			for (int j = i; j < numbers.length; j++) {
				twoValuesSum[count++] = numbers[i] + numbers[j];
			}
		}
		Arrays.sort(twoValuesSum);

		int answer = -1;
		for (int i = 0; i < numbers.length; i++) {
			for (int j = 0; j < numbers.length; j++) {
				if (binarySearch(twoValuesSum, numbers[i] - numbers[j])) {
					answer = Math.max(answer, numbers[i]);
				}
			}
		}
		System.out.println(answer);
	}

	private static boolean binarySearch(int[] arr, int value) {
		int l = 0;
		int r = arr.length - 1;
		while (l <= r) {
			int m = (l + r) / 2;
			if (arr[m] > value) {
				r = m - 1;
			} else if (arr[m] < value) {
				l = m + 1;
			} else{
				return true;
			}
		}
		return false;
	}
	
}