알고리즘 : hash table, brute force
시간복잡도: O(N^2) 만약 A, B, C, D ... 총 K 개의 배열이 존재한다면, 분할 정복을 활용해 hash table 을 만들 수 있고, O(N^logK) 시간복잡도 내에 해결할 수 있다.
풀이 설명 : 먼저 두 배열을 선택해 완전 탐색 기법을 통해 병합하여, 가능한 수를 key, 출현 빈도를 value로 하는 hash table을 만들 수 있다. 이때 단순히 병합 결과를 배열에 저장할 수 없는데, 가능한 수의 개수보다 범위가 월등히 높기 때문에 수를 index로 활용할 수 없기 때문이다. 이때 hash table을 활용하면 수를 key로 사용하여 공간을 절약할 수 있다. 이와 같이 배열 또는 hash table을 다른 hash table과 병합하는 방식으로 계속해서 hash table을 만들 수 있다. 또한 두 hash table을 병합하는 시간복잡도는 두 hash table의 크기의 곱과 같기 때문에, 크기가 작은 hash table끼리 순차적으로 곱해가면 된다. 이와 같은 방식으로 시간복잡도 크기를 줄일 수 있다. 한편 우리는 각 배열에서 선택한 원소의 합이 0이 되는 단일한 경우만 찾으면 되므로, 최종적으로 두 개의 hash table로 만든 후, 하나의 hash table의 원소에 대해 나머지 hash table의 원소와의 합이 0이 되는 경우가 존재하는지를 확인하면 되기 때문에 시간복잡도 min(N1,N2)로 계산할 수 있다.