백준 9847 자바 - 4SUM (BOJ 9847 JAVA)

문제 : 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개의 세트로 만들면 다음과 같다.

  

  AxB를 O(1)로 찾기 위해서는 Hash에 넣거나 배열로 표현해야 한다. 어떤걸로 표현해도 상관없다. 그 후 CxD의 결과를 순회하며 AxB의 해시 혹은 배열에서 합이 0이 되는 경우를 찾으면 된다. 다만 이 문제는 답이 되는 A,B,C,D의 원소 자체를 출력해야 하므로 그에대해서는 저장해두어야 한다.

 

  물론 '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();
    }
}