[파이썬] 백준 7453 : 합이 0인 네 정수 (골드2)

[파이썬] 백준 7453 : 합이 0인 네 정수 (골드2)

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

---

풀이

방향성 생각

• 투포인터 태그가 있긴한데 해싱이 조금 더 직관적인 풀이라고 생각한다.
• AB에서 N^2, CD 에서 N^2의 모든 경우의 수를 만든다.
• AB에 저장된 숫자로 CD에 매칭되는 숫자는 유일하니 이 경우를 카운팅하기

---

전체코드

from collections import defaultdict as dd
import sys

input = lambda : sys.stdin.readline().rstrip()
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)


# AB에서 가능한 조합의 최댓값 M을 찾는다. 등장횟수는 table에 기록
M = -float('inf')
table = dd(int)
for a in A:
    for b in B:
        v = a+b
        table[v] += 1
        M = max(M,v)

# C,D 배열을 정렬한다. 탐색을 하면서 가능한 조합은 숫자가 점점 커진다.
# M보다 커지면 더 이상 c와 남은 D의 조합을 탐색할 필요가 없다.
answer = 0
C.sort(); D.sort()
for c in C:
    find = False
    for d in D:
        v = c+d
        if -v in table:
            answer += table[-v]
            find = True
            last_v = v
        if find and last_v>M:
            break
print(answer)

# 첫 제출 코드
from collections import defaultdict as dd
import sys

input = lambda : sys.stdin.readline().rstrip()
N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
arr = list(zip(*arr))

temp1,temp2 = dd(int),dd(int)

for i in range(N):
    for j in range(N):
        temp1[arr[0][i]+arr[1][j]] += 1
        temp2[arr[2][i]+arr[3][j]] += 1

answer = 0
for a in temp1.keys():
    if -a in temp2:
        answer += temp1[a] * temp2[-a]
print(answer)

코멘트

• 시간 줄이는 아이디어는 어렵지않다.
• 정렬 + 투포인터로 풀어도되는데, 같은 숫자가 여러 번 등장해서 신경 쓸 부분은 있었을듯