[BOJ 7453] 합이 0인 네 정수 (Python)

풀이

처음에 완전탐색으로 A[a] + B[b] + C[c] + D[d] = 0인 경우를 모두 구하는 방식으로 접근하였다. 시간 복잡도는 O(N^4)으로 당연히 시간 초과가 발생한다.

문제의 포인트는 A[a] + B[b]의 리스트 1개, C[c] + D[d]의 리스트 1개로 총 2개의 리스트를 활용하는 다른 사람들의 풀이를 볼 수 있었다 (이 문제의 풀이를 봤을 때 '아차' 싶었다. 풀이를 본 후에 구현하는데 있어 어려움이 없었기 때문이였다...). 2개의 리스트를 활용하게 되면 O(N^4)의 시간 복잡도를 O(N^2)로 줄여준다. 그리고 Dictionary자료형을 활용하여 A[a] + B[b] + C[c] + D[d] = 0이 되는 쌍의 개수를 구해주었다.

다른 사람들의 풀이를 보았더니 이 문제가 이분 탐색 문제라고 한다. '사용하는 리스트를 반으로 줄여서 그런건가?'라는 생각이 든다. 원하는 값을 찾기 위해 반으로 쪼개고 탐색하고, 또 반으로 쪼개고 탐색하는 과정을 반복하는 것이 이분 탐색(O(logN))이라고 알고있는데, 왜 이 문제가 이분 탐색 문제인지는 정확히 모르겠다 (온전히 본인의 생각이다...).

코드

# Python3 시간 초과 / PyPy3 통과
import sys
from collections import defaultdict

input = sys.stdin.readline
n = int(input())
A, B, C, D = [], [], [], []
for _ in range(n):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

# A + B 배열과
# C + D 배열로 나누기 -> 시간 복잡도 줄이기 위해 (N^4 -> N^2)
first = defaultdict(int)
for i in range(n):
    for j in range(n):
        A_B = A[i] + B[j]
        first[A_B] += 1

answer = 0
for i in range(n):
    for j in range(n):
        C_D = C[i] + D[j]
        # (A + B) + (C + D) == 0일 때 key값에 대한 value만큼 더해준다.
        # (C + D)의 -1을 곱한값이 first에 있으면 A + B + C + D가 0이다.
        if first.get(-C_D):
            answer += first.get(-C_D)

print(answer)