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

문제 보기

[사용한 알고리즘]

구현, Dictionary

 

[문제 접근]

A[a], B[b]의 값의 덧셈으로 만들 수 있는 결과를 딕셔너리에 저장합니다. 그리고 C[c], D[d]로 만들 수 있는 값에 -를 붙인 값이 딕셔너리에 존재하는지 확인하여 최종적으로 A[a], B[b], C[c], D[d]의 합이 0인 쌍의 개수를 구하였습니다.

 

[알고리즘]

1. A[a]와 B[b]로 만들 수 있는 딕셔너리를 구현합니다.

 - 딕셔너리의 key와 value는 만들 수 있는 숫자와 해당 숫자의 개수입니다.

2. C[c]와 D[d]로 만들 수 있는 값에 -를 붙인 값이 해당 딕셔너리에 존재하는지 확인한 후 존재한다면 해당 key의 value 값을 더합니다.

 

[코드]

import sys


if __name__ == "__main__":
    n = int(input())
    array = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    a_list, b_list, c_list, d_list = list(), list(), list(), list()
    for i in range(n):
        for j in range(4):
            value = array[i][j]
            if j == 0:
                a_list.append(value)
            elif j == 1:
                b_list.append(value)
            elif j == 2:
                c_list.append(value)
            elif j == 3:
                d_list.append(value)

    ab = dict()

    # ab 가능한 합 계산
    for a in a_list:
        for b in b_list:
            ab[a + b] = ab.get(a + b, 0) + 1

    # cd 가능한 합 계산
    answer = 0
    for c in c_list:
        for d in d_list:
            answer += ab.get(-(c + d), 0)

    print(answer)