첫 시도
- N은 10^3이므로 x,y,z 3가지 경우의 수를 모두 확인하려면 10^9이므로 완탐 불가
- 해결방법을 찾지 못해 구글링
해결
- x+y+z = k일때 k를 만들 수 있는 경우의 수는 N^3
- x+y+z = k를 x+y = k-z로 바꾼다면 N^2으로 구현할 수 있음
- 추가로 x+y의 값이 저장되어 있는 배열에서 k-z값을 찾으려면 이분탐색을 사용해야 함 -> 완전탐색으로 찾으려면 시간초과
- 시간복잡도는 x+y의 경우의 수 * 이분탐색 -> O(N^2 (log N)^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.*;
import java.util.stream.Collectors;
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[] input = new int[N];
int[] sumArr = new int[N * N];
for(int i = 0; i < N; i++) {
input[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(input);
int idx = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
sumArr[idx++] = input[i] + input[j];
}
}
Arrays.sort(sumArr, 0, idx - 1); // 부분 정렬, 0부터 idx-1까지 정렬
for(int i = N -1; 0 <= i; i--){
for(int j = i; 0 <= j; j--){
//이진탐색, 원하는 값을 찾으면 해당 인덱스 값을 반환
if(Arrays.binarySearch(sumArr,0,idx -1,input[i]-input[j]) < 0) continue;
System.out.println(input[i]);
return;
}
}
}
}