[백준] 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이 되는 쌍의 개수를 출력한다.

​

입출력 예

input	output
6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45	5

​

접근법

네 리스트의 조합을 한번에 다루면 for문이 4개나 생기기 때문에, 시간복잡도가 O(n4)가 되버려서 시간이 엄청 오래걸립니다. 따라서 리스트를 2개씩 쪼개서 계산하면 됩니다. 즉, a리스트와 b리스트의 계산을 먼저 하고 a+b의 합과 부호가 반대인 수가 c+d의 합에 있다면, 0이 되는 조건입니다. 여기서 a+b에 -2가 두가 있을때, c+d에 2가 있다면, 0이 되는 조합은 총 2개이겠죠? 따라서

중복을 고려해주셔야합니다!

이를 딕셔너리로 만들어서 key는 a+b, value는 개수로 넣어주시면 됩니다. 이렇게 만들어진 딕셔너리에 -(c+d)가 존재하면 그 value만큼 카운트해주시면됩니다.

​

코드 제출하실때 pyp3로 제출하셔야합니다! python3로 제출하면 계속 실패가 뜨더라구요 ㅠㅠ

찾아보니까 python으로 성공한사람이 없다고해요... 이분 탐색을 써도 python3에서는 계속 실패가 뜨네요

​

나의 코드

import sys

number = int(sys.stdin.readline())
a_list, b_list, c_list, d_list = [], [], [], []
for _ in range(number):
    a, b, c, d = map(int,sys.stdin.readline().split())
    a_list.append(a); b_list.append(b); c_list.append(c); d_list.append(d)

a_b_dict = dict()
for a in a_list:
    for b in b_list:
        a_b_dict[a+b] = a_b_dict.get(a+b, 0) + 1

count = 0
for c in c_list:
    for d in d_list:
        count += a_b_dict.get(-(c+d),0)

print(count)