[백준/파이썬][Gold II] 합이 0인 네 정수 - 7453

[Gold II] 합이 0인 네 정수 - 7453

문제 링크

성능 요약

메모리: 680740 KB, 시간: 4056 ms

분류

이분 탐색, 중간에서 만나기, 정렬, 두 포인터

제출 일자

2025년 2월 24일 06:36:14

문제 설명

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

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

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2²⁸이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

풀이

def sol_7453() :
    n = int(input())
    res = 0
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr = list(map(sorted, zip(*arr)))

    AB = list(a + b for a in arr[0] for b in arr[1])
    CD = list(c + d for c in arr[2] for d in arr[3])
    AB.sort()
    CD.sort()

    left, right = 0, len(CD) - 1

    while left < len(AB) and right >= 0 :
        sumval = AB[left] + CD[right]
        if sumval == 0 :
            n_left, n_right = left + 1, right - 1
            while n_left < len(AB) and AB[left] == AB[n_left] :
                n_left += 1
            while n_right >= 0 and CD[right] == CD[n_right] :
                n_right -= 1

            res += (n_left - left) * (right - n_right)
            left, right = n_left, n_right

        elif sumval < 0 :
            left += 1

        else :
            right -= 1

    print(res)

sol_7453()

투 포인터를 활용한 풀이인 듯 한데, 아직 이해가 잘 되지 않는다. 풀이과정을 조금 더 생각해봐야겠다.