[파이썬] 백준 7453 : 합이 0인 네 정수 (골드2)
풀이
방향성 생각
- 투포인터 태그가 있긴한데 해싱이 조금 더 직관적인 풀이라고 생각한다.
- 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)
코멘트
- 시간 줄이는 아이디어는 어렵지않다.
- 정렬 + 투포인터로 풀어도되는데, 같은 숫자가 여러 번 등장해서 신경 쓸 부분은 있었을듯
댓글