[코드트리 챌린지] 2주차 - HashMap / 원소의 합이 0

https://www.codetree.ai/cote/16/problems/the-sum-of-the-elements-is-0?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 분석:

이 문제는 네 개의 수열 A, B, C, D에서 각 수열에서 한 원소씩 선택하여 합한 값이 0이 되는 조합의 수를 찾는 문제입니다. 일반적으로 모든 조합을 시도하여 문제를 해결한다면, 시간 복잡도는 O(n^4)이 되어 n=5000의 최대 크기에서는 시간 내에 해결이 어렵습니다.

따라서 효율적인 방법을 찾아야 합니다. 이 문제의 핵심 아이디어는 두 개의 수열을 묶어서 처리하는 것입니다. A와 B의 조합, 그리고 C와 D의 조합으로 나누어 각 조합에서 나올 수 있는 합의 빈도수를 계산합니다. 이후 A와 B의 조합에서 나온 합과 C와 D의 조합에서 나온 합이 서로 반대 부호이고 절대값이 같은 경우를 찾아서 그 경우의 수를 합산하면 됩니다.

풀이 방법:

1. 빈도수 계산: 두 수열 A와 B를 돌면서 각 원소의 합의 빈도수를 딕셔너리에 저장합니다. 이를 seq_dicts_A에 저장합니다.
2. 빈도수 계산: 마찬가지로 두 수열 C와 D를 돌면서 각 원소의 합의 빈도수를 딕셔너리에 저장합니다. 이를 seq_dicts_B에 저장합니다.
3. 서로 반대 부호의 합 찾기: seq_dicts_A에서 나온 합과 seq_dicts_B에서 나온 합 중 서로 반대 부호이고 절대값이 같은 경우를 찾아 그 경우의 수를 합산합니다.

코드

n = int(input())

seq_dicts_A = [{}, {}]
seq_dicts_B = [{}, {}]

cnt = 0
# A와 B의 원소 빈도수 계산
for i in range(2):
    for n in list(map(int,input().split())):
        if n in seq_dicts_A[i]:
            seq_dicts_A[i][n] += 1
        else:
            seq_dicts_A[i][n] = 1
# C와 D의 원소와 A, B의 원소 합의 빈도수 계산
for i in range(2):
    for n in list(map(int,input().split())):
        for n2 in seq_dicts_A[i]:
            if n + n2 in seq_dicts_B[i]:
                seq_dicts_B[i][n+n2] += seq_dicts_A[i][n2]
            else:
                seq_dicts_B[i][n+n2] = seq_dicts_A[i][n2]

# 합이 0이 되는 경우의 수 계산
for n in seq_dicts_B[0]:
    if n*-1 in seq_dicts_B[1]:
        cnt += seq_dicts_B[1][n*-1]*seq_dicts_B[0][n]

print(cnt)

코드 설명:

• seq_dicts_A와 seq_dicts_B는 각각 A와 B의 합, C와 D의 합의 빈도수를 저장하는 딕셔너리입니다.
• A와 B의 원소들의 합의 빈도수를 계산하여 seq_dicts_A에 저장합니다.
• C와 D의 원소들의 합의 빈도수를 계산하여 seq_dicts_B에 저장합니다.
• seq_dicts_A의 각 합에 대해 seq_dicts_B에서 그 합의 반대 부호의 빈도수를 찾아 그 빈도수만큼 경우의 수를 합산합니다.

 이 풀이의 시간 복잡도는 대략 O(n^2)입니다. 각 수열에서의 조합을 계산하는 데 O(n^2)의 시간이 걸리고, 딕셔너리에서 키를 찾는 데 걸리는 시간은 평균적으로 O(1)입니다. 따라서 전체 시간 복잡도는 O(n^2)으로, n=5000의 최대 크기에서도 충분히 빠른 시간 내에 문제를 해결할 수 있습니다.

위의 문제를 풀어보고 지난 실력 진단에서 나의 부족한 점을 공부하고 다시 시험을 치니 높은 점수를 얻을 수 있었다. 남은 6주동안 더 많은 공부를 해봐야겠다.