📚 7453 - 합이 0인 네 정수

합이 0인 네 정수

이해

이 문제는 무엇보다 시간을 잘 줄여야 한다.
단순하게 반복문 4개를 돌릴 경우 O(4*n)로 틀린 답이 된다.

그러면 어떠한 방법이 있는가?
a, b, c, d 총 합이 0이어야 한다.
이는 a + b와 c + d의 총 합이 0이라는 의미이기도 하다.
반복문 두개를 따로 돌려서 합이 0이 되는 쌍의 개수를 출력하면 된다.

나도 검색을 하다 알게 되었는데 이러한 이분 탐색을 풀어야 할 때는, 딕셔너리를 사용하면 좋은 것 같다.

소스

import sys

read = sys.stdin.readline

n = int(read())

a = []
b = []
c = []
d = []

for _ in range(n):
    x1, x2, x3, x4 = map(int, read().split())
    a.append(x1)
    b.append(x2)
    c.append(x3)
    d.append(x4)

abcd_sum = dict()

for in_a in a:
    for in_b in b:
        abcd_sum[in_a + in_b] = abcd_sum.get(in_a + in_b, 0) + 1

result = 0

for in_c in c:
    for in_d in d:
        result += abcd_sum.get(-(in_c + in_d), 0)

print(result)

pypy3으로 제출해야 한다.