백준 7453 합이 0인 네 정수

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 

정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

https://www.acmicpc.net/problem/7453

---

풀이 : 

1. O(n^2)이 16,000,000이므로 A+B 모든 경우를 unordered_map에 insert

2. -(C+D)에 대해서 탐색

But, 해시 충돌로 인한 시간 초과

---

1. A+B 모든 경우를 배열에 담고 정렬 O(n^2logn^2)

2. 이분탐색 (upper_bound, lower_bound) 이용

통과

---

1. unordered_map을 사용하지 않고 hash function을 생성해 Clear!!