[백준] 7453번 : 합이 0인 네 정수

7453번: 합이 0인 네 정수

7453번: 합이 0인 네 정수

🤔 문제분석

투포인터 및 정렬문제로, A,B,C,D를 입력받고, A배열과 B배열을 합하여 AB배열을 만들고, C배열과 D배열을 합하여 CD배열을 만듭니다. 만든 배열을 정렬을하고, AB는 왼쪽으로부터 오른쪽으로 CD는 오른쪽으로부터 왼쪽으로 순회해 가면서 두개의 값이 0보다 클경우, 작을경우, 0과 같을 경우로 분기하여 문제를 해결합니다. 여기서 중요한점은 0이 되었을때 AB 혹은 CD값이 중복된 값을 카운팅 해주어야합니다. 예를들어 AB가 [55,55,55,55] CD가 [-55, -55, -55, -55]가 있다고 할때, 경우의 수는 총 4*4인 16가지가 되기때문에 중복된 값을 카운팅하여 결과를 누적해야합니다.

💻 코드

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)
    
AB = []
CD = []
for i in range(N):
    for j in range(N):
        AB.append((A[i]+B[j]))
        CD.append((C[i]+D[j]))
        
pleft = 0
pright = len(CD) - 1
AB.sort()
CD.sort()
ans = 0

def find_cnt(value, arr):
    start = 0
    end = len(arr)-1
    left_idx = -1
    
    while end >= start:
        mid = (start + end) // 2
        if arr[mid] > value:
            end = mid - 1
        else:
            left_idx = mid
            start = mid + 1
    
    start = 0
    end = N*N-1
    right_idx = -1
    while end >= start:
        mid = (start + end) // 2
        if arr[mid] >= value:
            right_idx = mid
            end = mid - 1
        else:
            start = mid + 1
    
    return right_idx - left_idx + 1

while pleft < len(AB) and 0 <= pright:
    cost = AB[pleft] + CD[pright]
    if cost == 0:
        check_left = AB[pleft]
        check_right = CD[pright]
        left_cnt = 0
        right_cnt = 0
        while pleft < len(AB) and AB[pleft] == check_left:
            left_cnt += 1
            pleft += 1
            
        while 0 <= pright and CD[pright] == check_right:
            right_cnt += 1
            pright -= 1
        
        ans += left_cnt * right_cnt
        
    elif cost > 0:
        pright -= 1
    else:
        pleft += 1
        
print(ans)

🎯 피드백 및 개선사항

직전에 투포인터 문제를 해결했어서 문제를 빠르게 풀 수 있었습니다. 그러나 과연 문제를 처음 접했을때 투포인터로 문제를 해결 할 수 있을지 🥲

번외로 딕셔너리 자료구조를 활용하여 문제를 해결하는 방법도 있습니다.

from collections import defaultdict
import sys
input = sys.stdin.readline

ab_sum = defaultdict(int)

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)
    
    
for a in A:
    for b in B:
        ab_sum[a+b] += 1

ans = 0
for c in C:
    for d in D:
        ans += ab_sum[-(c+d)]
        
print(ans)