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

 

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

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

 

 

 

 

 

 

난이도

골드2

 

 

 

 

 

내 코드

import sys

n = int(sys.stdin.readline())
answer = 0
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)

x = []
y = []

for i in range(n) :
    for j in range(n) :
        x.append(A[i] + B[j])

for i in range(n) :
    for j in range(n) :
        y.append(C[i] + D[j])

x.sort()
y.sort()

# 여기서 투포인터
left = 0
right = len(y)-1

while True :
    tmp = x[left] + y[right]
    if tmp == 0 :
        # 중복처리
        cnt_x = 1
        cnt_y = 1
        ll = left+1
        while ll < len(x) :
            if x[left] == x[ll] :
                cnt_x += 1
                left = ll
                ll += 1
            else :
                break
        rr = right-1
        while rr > -1 :
            if y[right] == y[rr] :
                cnt_y += 1
                right = rr
                rr -= 1 
            else :
                break

        answer += (cnt_x * cnt_y)
        if left < len(x) - 1:
            left += 1
        elif right > 0 :
            right -= 1
        else :
            break
    elif tmp < 0 :
        if left < len(x) - 1 :
            left += 1
        else :
            break
    else :
        if right > 0 :
            right -= 1
        else :
            break

print(answer)

 

 

 

 

 

 

풀이과정

이 문제는 투포인터 문제인데 배열이 4개나 되어서 어떻게 접근할지 고민했다.

예전에 배열이 3개인 문제에서 하나의 배열은 for문으로 돌면서 남은 2개의 배열을 투포인트로 접근했던 게 생각나서 처음에는 A배열과 B배열을 이중for문으로 돌아가며 C와 D는 그 때 마다 투포인트로 접근해보았다.

결과는 시간초과.. 시간제한이 12초였는데도 시간이 턱없이 부족했다. n^3 이라서 예상했다.

 

그래서 다음으로 생각한 방법은 A+B, C+D 의 값을 가진 두 배열을 만들고, 그 두 배열로 투포인터를 사용하는것이었다.

주의할 점은 합이다보니 배열에서 동일한 조합이 여러번 나올 수 있는데 이걸 각각 세야 하니 그 부분은 while 문으로 같은 값이 각각 몇 번 나오는지 cnt 해서 처리했다.

이 방법은 n^2 + n^2 + n^2 => n^2 방법으로 위 방법보다 시간을 줄일 수 있어서 pypy로 통과했다!

 

하지만 python 으로는 통과하지 못했다는 사실..ㅠㅠ