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

문제

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

알고리즘

투 포인터 or 해시 맵, 중간에서 만나기

풀이

a,b,c,d로 4중 for문을 돌리면 O(N^4)의 경우 시간초과로 터진다.

이걸 a,b와 c,d로 나눠서 각각 O(N^2)으로 해결하고, 분리된 ab와 cd를 해시맵 또는 투포인터로 연결시켜주면, O(N^2)으로 문제를 해결할 수 있다.

해시맵보다는 투포인터를 추천한다. 해시맵에 값이 너무 들어가는 경우 해시 충돌로 인해 속도가 오히려 느려진다.

코드

from sys import stdin
input = 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 = []
CD = []

for a in A:
    for b in B:
        AB.append(a + b)

for c in C:
    for d in D:
        CD.append(c + d)

AB.sort()
CD.sort(reverse=True)

i, j = 0, 0
cnt = 0
len_ab, len_cd = len(AB), len(CD)

while i < len_ab and j < len_cd:
    current_ab = AB[i]
    current_cd = CD[j]
    total = current_ab + current_cd

    if total == 0:
        ab_count = 0
        while i < len_ab and AB[i] == current_ab:
            ab_count += 1
            i += 1

        cd_count = 0
        while j < len_cd and CD[j] == current_cd:
            cd_count += 1
            j += 1

        cnt += ab_count * cd_count

    elif total < 0:
        i += 1
    else:
        j += 1

print(cnt)