문제 : boj9847
1. Brute Force로 가능한가?
4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다.
2. 문제를 단순화 해보자
그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까?
모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정도가 된다.
좀 더 빠르게 해보자면 X에 대해 Hash 혹은 값에 대한 배열로 어떠한 수가 있는지 메모리를 더 써서 기록해둔다. 그렇게 하면 Y를 순회하며 각 O(1)로 합이 0이 되는 수를 찾을 수 있다. 그럼 O(N[전처리] + N[순회]*1[찾기] 정도가 된다.
3. 다시 문제의 4개의 합으로 돌아와서 '2'를 적용해보자.
만약 4개의 세트를 2개의 세트로 적정한 시간 내에 만들 수 있다면 '2'를 적용해볼 수 있다. A와 B, C와 D를 나눠서 보자. 각각을 완전탐색 하는 경우 각각 O(500^2)으로 가능하다. 그럼 A와B를 합쳐 X를 만들고, C와D를 합쳐 Y를 만든다면 '2'를 적용하여 O(N^2[전처리] + N^2[순회]*1[찾기]) = O(N^2) 으로 가능해진다! 이게 이 문제의 키 아이디어이다. 아이디어만 찾으면 문제가 엄청나게 간단해지는데, 그냥 풀려면 상당히 어렵게 느껴진다.
문제의 '예시 입력 1'를 A,B와 C,D를 합쳐 2개의 세트로 만들면 다음과 같다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
AxB를 O(1)로 찾기 위해서는 Hash에 넣거나 배열로 표현해야 한다. 어떤걸로 표현해도 상관없다. 그 후 CxD의 결과를 순회하며 AxB의 해시 혹은 배열에서 합이 0이 되는 경우를 찾으면 된다. 다만 이 문제는 답이 되는 A,B,C,D의 원소 자체를 출력해야 하므로 그에대해서는 저장해두어야 한다.
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
물론 '2'에서 설명한 내용 중 AxB와 CxD에 대해 이분탐색으로 진행하는 경우도 이 문제에서 시간상 유효하다. 그 경우 O(N^2 log(N^2))이 된다.
코드 : github
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int[] abcd = new int[4];
for (int i = 0; i < 4; i++) abcd[i] = Integer.parseInt(st.nextToken());
int[] tmp = new int[abcd[0]];
for (int i = 0; i < abcd[0]; i++) tmp[i] = Integer.parseInt(br.readLine());
HashMap<Integer, String> hm = new HashMap<>();
for (int i = 0; i < abcd[1]; i++) {
int b = Integer.parseInt(br.readLine());
for (int j = 0; j < abcd[0]; j++) {
hm.put(tmp[j] + b, tmp[j] + " " + b);
}
}
tmp = new int[abcd[2]];
for (int i = 0; i < abcd[2]; i++) tmp[i] = Integer.parseInt(br.readLine());
for (int i = 0; i < abcd[3]; i++) {
int d = Integer.parseInt(br.readLine());
for (int j = 0; j < abcd[2]; j++) {
if (hm.containsKey(-(tmp[j]+d))) {
System.out.println(hm.get(-(tmp[j]+d)) + " " + tmp[j] + " " + d);
return;
}
}
}
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
'PS > BOJ' 카테고리의 다른 글
백준 11060 자바 - 점프 점프 (BOJ 11060 JAVA) (0) | 2022.01.10 |
---|---|
백준 2331 자바 - 반복수열 (BOJ 2331 JAVA) (0) | 2022.01.09 |
백준 20949 자바 - 효정과 새 모니터 (BOJ 20949 JAVA) (0) | 2022.01.06 |
백준 1298 자바 - 노트북의 주인을 찾아서 (BOJ 1298 JAVA) (0) | 2022.01.06 |
백준 2188 자바 - 축사 배정 (BOJ 2188 JAVA) (0) | 2022.01.05 |
댓글