백준 7453: 합이 0인 네 정수

문제

---

풀이

 

백준 분류 상으로는 이분 탐색을 사용하는 문제라 되어 있으나 다소 다르게 풀이

이분 탐색 버전으로 풀어보지 않아서 무엇이 더 효율적인 풀이인지는 모르겠다.

A, B, C, D, = [], [], [], []
for i in range(n):
    arr = list(map(int, input().split()))
    A.append(arr[0])
    B.append(arr[1])
    C.append(arr[2])
    D.append(arr[3])

일단 입력을 열로 분리해서 A, B, C, D 배열을 각각 만들어 주었다. 생략해도 무방한 단계지만 직관성을 위해...

 

A, B 원소의 조합을 구한 뒤 해당 원소와 절댓값이 같고 부호가 다른 값을 C, D 조합에서 찾는 방식으로 풀이한다.

A, B, C, D를 전부 분리해서 생각하면 뭐든 4번씩 계산해야 돼서 복잡해질 것 같았으므로 AB/CD를 묶어 생각하는 것

AB = defaultdict(int)   # combination of A, B

for i in range(n):
    for j in range(n):
        AB[A[i] + B[j]] += 1

우선 딕셔너리에 A[i] + B[i]로 가능한 조합을 모두 넣어 주고

res = 0 # count
for i in range(n):
    for j in range(n):
        if -1 * (C[i] + D[j]) in AB.keys():
            res += AB[-1 * (C[i] + D[j])]

가능한 모든 C + D 조합에 대해 AB 딕셔너리에서 해당 값에 *(-1)한 것을 탐색

CD도 딕셔너리로 만들지 않는 이유는 그렇게 했을 때 시간 초과 오류가 떴기 때문이다

 

아래는 오류 AB, CD 딕셔너리를 각각 만들었을 때 오류 코드이다.

import sys
from collections import defaultdict

input = sys.stdin.readline

n = int(input())

# separate A, B, C, D
A, B, C, D, = [], [], [], []
for i in range(n):
    arr = list(map(int, input().split()))
    A.append(arr[0])
    B.append(arr[1])
    C.append(arr[2])
    D.append(arr[3])

AB = defaultdict(int)   # combination of A, B
CD = defaultdict(int)   # combination of C, D
for i in range(n):
    for j in range(n):
        AB[A[i] + B[j]] += 1
        CD[C[i] + D[j]] += 1

res = 0 # count
for k, v in AB.items():
    if -1 * k in CD.keys():
        res += v * CD[-1 * k]

print(res)

딕셔너리는 해시테이블이라 시간복잡도가 좋은 것으로 알고 있는데 왜 이런 문제가 발생하는지는 잘 모르겠으나

어쨌든 배열로 바로 look-up할 수 있도록 수정하면 풀린다

 

전체 코드

import sys
from collections import defaultdict

input = sys.stdin.readline

n = int(input())

# separate A, B, C, D
A, B, C, D, = [], [], [], []
for i in range(n):
    arr = list(map(int, input().split()))
    A.append(arr[0])
    B.append(arr[1])
    C.append(arr[2])
    D.append(arr[3])

AB = defaultdict(int)   # combination of A, B

for i in range(n):
    for j in range(n):
        AB[A[i] + B[j]] += 1

res = 0 # count
for i in range(n):
    for j in range(n):
        if -1 * (C[i] + D[j]) in AB.keys():
            res += AB[-1 * (C[i] + D[j])]

print(res)

그렇다고 코드가 가벼워지는 것은 아님