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

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

7453번: 합이 0인 네 정수

 

 

문제 해결

• 먼저 n행이면 배열의 크기가 n이라는 것이고 열은 각각 A,B,C,D를 나타낸다는 것을 알아야한다.
• A,B,C,D를 각각 원소를 찾기에는 (O($n^{4}$))의 시간복잡도가 나오기 때문에 가급적 줄여야한다.
• 따라서 AB원소의 합을 ab에 CD원소의 합을 cd에 넣어서 줄일려고 하였다.(O($n^{2}$))
• 그리고 원소를 각각 오름차순으로 배열을 하고 ab는 인덱스0부터 cd는 인덱스 (len(cd)-1)부터 시작하여 합이 0이 되는 부분을 투포인터를 이용하여 푸는 것이다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
ab, cd = [], [] # A열과 B열의 원소의 합을 원소로 갖는 ab, C열과 D열의 원소의 합을 원소로 갖는 cd
for i in range(n):
    for j in range(n):
        ab.append(graph[i][0] + graph[j][1])
        cd.append(graph[i][2] + graph[j][3])
ab.sort()
cd.sort()
i,j = 0, len(cd)-1
answer = 0
while i<len(ab) and j>=0:
    if ab[i]+ cd[j] ==0:
        nexti, nextj = i+1, j-1
        while nexti < len(ab) and ab[i] == ab[nexti]:
            nexti += 1
        while nextj >= 0 and cd[j] == cd[nextj]:
            nextj -= 1
        answer += (nexti-i)*(j-nextj)
        i, j = nexti, nextj
    elif ab[i] + cd[j]>0:
        j-= 1
    else:
        i += 1
print(answer)