백준 7453 - 합이 0인 네 정수 (Python)

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

7453번: 합이 0인 네 정수

 

어떻게 푸는지 몰라서 검색을 해본 결과, a,b,c,d의 조합을 전부다 구하면 O(n^4)의 시간이 걸리기 때문에 a+b+c+d = 0을 변형해서 a+b = -(c+d)로 바꿔서 a와 b의 조합, 그리고 c와 d의 조합을 각각 O(n^2)의 시간에 구해서 풀면 되는 문제였다. 그리고 파이썬에서 제공해주는 dict()를 사용하면 dict는 해쉬 알고리즘을 이용해서 O(1)만에 원하는 값을 찾을 수 있기 때문에 이렇게 풀면 된다. dict 대신 defaultdict(int)를 사용하면 더 빠른 시간내에 풀리지만 {}를 이용하면 시간초과가 난다.

---

 Python

from collections import defaultdict
answer = 0
n = int(input())
a = [0] * n
b = [0] * n
c = [0] * n
d = [0] * n
for i in range(n):
    a[i], b[i], c[i], d[i] = map(int, input().split())
 
added = defaultdict()
 
for i in range(len(a)):
    for j in range(len(b)):
        if a[i] + b[j] not in added:
            added[a[i]+b[j]] = 1
        else:
            added[a[i]+b[j]] += 1
 
for i in range(len(c)):
    for j in range(len(d)):
        if -(c[i]+d[j]) in added:
            answer += added[-(c[i]+d[j])]
 
print(answer)