백준 7453 합이 0인 네 정수 Python 3

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

7453번: 합이 0인 네 정수

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ7453.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
N = int(sys.stdin.readline())
A, B, C, D = [], [], [], []
for _ in range(N):
    a, b, c, d = map(int, sys.stdin.readline().split())
    A.append(a); B.append(b); C.append(c); D.append(d)

sum1 = dict()
for a in A:
    for b in B:
        sum1[a+b] = sum1.get(a+b, 0) + 1
cnt = 0
for c in C:
    for d in D:
        cnt += sum1.get(-(c+d), 0)
print(cnt)

---

풀이 과정

풀이 시간 55분

최대 4000의 크기를 갖는 4개의 배열의 값의 조합을 구하는 문제이다.

4차 for문으로 하면 4000^4이므로 당연히 시간초과가 나기 때문에, 2개씩 나누어 합을 구하고 절댓값은 같지만 부호가 다른 경우를 구하여 문제를 풀 수 있다.(이 역시도 Python3으로는 시간초과가 나기 때문에 Pypy3으로 돌려야한다,,)

 

또한, 처음에는 defaultdict를 사용해줬는데 이 경우도 역시 시간초과가 났다.

데이터의 크기에 따라 defaultdict를 사용하는 경우와 dict를 사용하는 경우, 속도가 다르기 때문이다.

데이터가 적은 경우에는 defaultdict가 빠르지만, 데이터가 많은 경우 dict가 빠르다고 한다.

이에 관한 참고는 아래 링크를 확인하면 된다.

 

import sys
N = int(sys.stdin.readline())
A, B, C, D = [], [], [], []
for _ in range(N):
    a, b, c, d = map(int, sys.stdin.readline().split())
    A.append(a); B.append(b); C.append(c); D.append(d)

sum1 = dict()
for a in A:
    for b in B:
        sum1[a+b] = sum1.get(a+b, 0) + 1
cnt = 0
for c in C:
    for d in D:
        cnt += sum1.get(-(c+d), 0)
print(cnt)
#시간복잡도 = O(N^2), 공간복잡도 = O(N)

 

 시간복잡도는 N^2이고 최대 N은 4000이기 때문에 1초 언저리로 볼 수 있겠지만, 실제 실행 결과를 보면 거의 11초가 소요된 것을 확인 할 수 있다.

게시판을 살펴보니, dict의 시간복잡도가 평균 O(1)이라고 말하지만, 사실상 그 뒤에는 어마어마하게 큰 상수가 숨겨져있다고 한다.

---

참고

• https://stackoverflow.com/questions/19629682/ordereddict-vs-defaultdict-vs-dict

OrderedDict vs defaultdict vs dict