7453-합이 0인 네 정수

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

7453번: 합이 0인 네 정수

문제 설명만 보면 무언가 흔히 봤던 문제 같지만 배열이 4개로 나누어져 있다. 거기다 입력값은 최대 4000개까지 가능해서 왠만한 방식으로는 그냥 바아아로 시간초과가 나버린다. 여러 방식들을 시도해 보았으나 가장 마음에 드는 방법은 역시 딕셔너리를 쓰는 거였다. 문제를 풀어볼수록 파이썬에 딕셔너리가 있어서 정말 감사하다~ 는 생각이 들었다. 특정 이분 탐색 문제는 조금만 코드를 조정해 딕셔너리를 사용해 원소를 찾는 방식으로 바꾸면 시간을 훨씬 단축할 수 있다. 

 

이 문제 같은 경우에는 총 4 세트로 받은 배열들을 둘둘씩 짝지어 총 두 개의 배열로 바꾸고, 첫번째 배열의 원소들을 딕셔너리에 저장한 후에 두번째 배열에서는 해당 원소가 딕셔너리에 있는 값과 역수 관계인지 확인을 하면서 진행하면 다른 풀이 방식보다 훨씬 간결한 코드를 작성할 수 있다. 입력받는 코드를 제외하면 대략 10줄 정도밖에 되지 않아서 코드를 보면 바로 이해가 갈 것이다.

import sys
input = sys.stdin.readline
n = int(input())
A, B, C, D = [], [], [], []
for _ in range(n):
    tmpinput = list(map(int, input().split()))
    A.append(tmpinput[0])
    B.append(tmpinput[1])
    C.append(tmpinput[2])
    D.append(tmpinput[3])
dic = {}
for a in A:
    for b in B: 
        if a+b in dic:
            dic[a+b] += 1
        else:
            dic[a+b] = 1
cnt = 0
for c in C:
    for d in D:
        if -(c+d) in dic:
            cnt += dic[-(c+d)]

print(cnt)