백준 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;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 10816 숫자 카드 2 (HashMap과 BinarySearch를 이용한 풀이) (0) | 2023.07.04 |
---|---|
백준 2470 두 용액 (JAVA 자바 풀이: 이분 탐색 활용) (0) | 2023.07.04 |
백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) (0) | 2023.07.03 |
백준 17232 생명 게임 (JAVA 자바 풀이) | 누적합 배열 (0) | 2023.07.03 |
백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이) (0) | 2023.07.02 |