[백준] 7453번 - 합이 0인 네 정수 (파이썬)

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

# 합이 0인 네 정수
import sys
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)

AandB = []
for a in A:
    for b in B:
        AandB.append(a+b)
AandB.sort()

CandD = []
for c in C:
    for d in D:
        CandD.append(c+d)
CandD.sort()

result = 0
left, right = 0, len(CandD)-1
sum = 0
while 0 <= right and left < len(AandB):
    sum = AandB[left] + CandD[right]
    if sum < 0:
        left += 1
    elif sum > 0:
        right -= 1
    else:
        x = 1
        for i in range(left+1, len(AandB)):
            if AandB[left] == AandB[i]:
                x += 1
            else:
                break
        y = 1
        for i in range(right-1, -1, -1):
            if CandD[right] == CandD[i]:
                y += 1
            else:
                break
        result += x*y
        left += x
        right -= y

print(result)

 

이진탐색

1. A,B,C,D를 입력을 받는다

2. 이진탐색을 하기 위해서 A와 B를 묶고 정렬, C와 D를 묶고 정렬

3. 이진탐색

    - AandB는 왼쪽부터, CandD는 오른쪽부터 진행

    - 둘의 합(sum) < 0 이면, left += 1

    - sum > 0 이면, right -= 1

    - sum == 0 이면, 현재값과 같은 값의 아이들의 개수만큼 left,right 바꿔주고 result += 곱

4. result 출력

 

4개의 리스트를 어떻게 처리할까 생각하느라 오래걸렸다.