합이 0인 네 정수 ( 7453 번 )

7453번: 합이 0인 네 정수

 

---

🧠 알고리즘

• 해시맵(Hash Map, Counter)을 이용한 투포인터 방식의 변형 (Meet in the Middle 기법)

 

✔️ 동작 방식

• 배열 A, B에서 가능한 모든 합 a+ba+ba+b를 구해 Counter에 저장한다. (중복 합은 빈도수로 누적)
• 배열 C, D에서 가능한 모든 합 c+dc+dc+d를 구하면서, −(c+d)-(c+d)−(c+d)가 A+B 합에 몇 번 등장했는지 확인한다.
• 등장 횟수만큼 결과값에 더해, 최종적으로 합이 0이 되는 쌍의 개수를 구한다.

---

 

🧾 코드

import sys
from collections import Counter

def _main(n):
    answer = 0
    
    a, b, c, d = [], [], [], []
    for _ in range(n):
        x1, x2, x3, x4 = map(int, sys.stdin.readline().rstrip().split())
        a.append(x1)
        b.append(x2)
        c.append(x3)
        d.append(x4)

    ab = Counter()
    for i in a:
        for j in b:
            ab[i + j] += 1

    for i in c:
        for j in d:
            answer += ab[-(i + j)]    
    
    return answer
    
n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for i in a : a 와 b 를 순회하며 가능한 합 해시맵에 기록 ( 이차형 시간 복잡도 )
    for j in b :

for i in c : c 와 d 를 순회하며 0 이되는 경우의 수 찾기 ( 이차형 시간 복잡도 )
    for j in d :
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )