Baekjoon 7453. 합이 0인 네 정수 / Python

7453. 합이 0인 네 정수

난이도 : 골드 2
소요 시간 : 40분
날짜 : 2024.12.20
언어 :Python
알고리즘 유형 : 이분탐색, 투포인터, 정렬

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 숫자를 담은 배열 A, B, C, D가 주어진다.
2. A에서 숫자 하나(a), B에서 숫자 하나(b), C에서 숫자 하나(c), D에서 숫자하나(d)를 골라서
3. 합(a + b + c + d)이 0이 되는 쌍의 개수를 찾는다.

2. 해결 방식

1. 우선 숫자의 개수는 최대 4000개이다.
2. 완탐 시간복잡도 O(n^4) : 4000^4 = 256,000,000,000,000 -> 약 250만 초가 걸린다.......
3. 투포인터 알고리즘을 사용해서 해결했다.
4. 우선 a + b와 c + d 의 순서쌍을 모두 찾는다. (시간복잡도 O(2 * n ^2) = 32,000,000 -> 0.3초)
5. 그 다음에는 투포인터 알고리즘을 위해 두 순서쌍을 정렬한다. (시간복잡도 O(2* n) = 32,000,000 -> 0.3초, 참고로 여기서 n은 4000이 아니라, 순서쌍집합의 크기인 16,000,000이다.)
6. 나는 더해서 0을 구하지 않고, (a + b)와 -(c + d)의 배열을 만들어서 같은 값인 경우에 쌍을 찾은 것으로 했다.
7. 그렇기 때문에 포인터가 양쪽이 아니라, 같은 지점에서 시작해야한다.

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

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 = [a + b for a in A for b in B]  # 16,000,000 a+b순서쌍
CD = [-(c + d) for c in C for d in D]  # 16,000,000 -c-d순서쌍

# 정렬
AB.sort()
CD.sort()
res = 0

i, j = 0, 0

# 투포인터
while i < len(AB) and j < len(CD):
    if AB[i] == CD[j]:
        i_tmp, j_tmp = i, j
        value = AB[i]

        while i < len(AB) and AB[i] == value:
            i += 1
        while j < len(CD) and CD[j] == value:
            j += 1

        res += (i - i_tmp) * (j - j_tmp)

    elif AB[i] > CD[j]:
        j += 1
    else:
        i += 1

print(res)