[백준] 7453 합이 0인 네 정수, python

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

 

 

 

 

 

a*b*c*d의 모든 경우의 수를 확인하게 되면 4000⁴ 가 되어 시간초과가 난다.

그래서 처음에는 A와 B의 합 배열 AB와 C와 D의 합 배열 CD를 만들어 AB에 있는 값에 -1을 곱한 값이 CD에 있으면 하나씩 세는 방법으로 풀었다.

여기서 합 배열을 구할 때 중복된 숫자가 있을 때를 가정하여 (합, 등장 횟수)를 딕셔너리로 저장했다.

하지만 C와 D의 합 배열을 생성하게 되면 추가적인 메모리 낭비와 이후 생성된 CD배열과 AB배열 비교에서 연산을 한번 더하게 되는 문제가 발생한다.

따라서 CD배열을 직접 생성하는 대신, C와 D의 합을 계산해 바로 AB합배열에 있는지 체크하면서 개수를 추가해 주면 된다.

 

기존 딕셔너리에 저장하게 되면 딕셔너리에 없는 값을 접근하려 하면 에러가 발생한다.

collections에 defatuldict를 사용하면 자동으로 없는 값일 때 int면 0, list면 빈배열, set이면 빈 set을 할당해 준다.

collections에 Counter을 사용해도 동일한 방법으로 해결할 수 있다. Counter은 list, deque, 문자열 등 반복가능한 객체의 요소의 등장 횟수를 세어 (key:요소, value: 등장 횟수)를 딕셔너리와 비슷한 구조로 반환해 준다.

 

또한 단순 반복연산이 많은 경우 같은 코드라도 PyPy3으로는 통과했는데 python 3은 시간초과가 발생한다.

이는 PyPy3는 JIT(Just-In-Time 컴파일) 방식을 사용하는데, JIT방식은 처음에는 기존 파이썬과 동일한 인터프리 방식으로 실행되지만 반복되는 부분을 기계어로 변환하여 속도가 더 빠르다. 그래서 단순 반복 연산 중심인 경우에는 PyPy3을 사용하는 것이 좋다. 하지만 모든 경우에서 PyPy3이 빠른 건 아니다. 코드의 길이가 짧거나 반복연산이 많이 없는 경우에는 JIT 준비 과정 때문에 python 3 가 빠르다.

 

 

import sys
from collections import Counter, 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)

counterAB = Counter()
# counterAB = defaultdict(int)

# a배열과 b배열의 합: 등장횟수 생성
for i in range(n):
    Ai = A[i]
    for j in range(n):
        counterAB[Ai+B[j]] += 1

answer = 0

# c와 d의 합을 구하고 바로 그 값이 ab합배열에 있는지 학인하고 있으면 개수를 추가한다.
for i in range(n):
    Ci = C[i]
    for j in range(n):
        answer += counterAB.get(-(C[i]+D[j]),0)

print(answer)