[코드트리 문제] 두 수의 합 문제

틀렸던 문제는 두 수의 합과 유사하지만 조금 더 복잡한 문제였다.

먼저 기초가 되는 두 수의 합 문제를 풀어보면서 응용할 수 있도록 공부해서 다음엔 풀 수 있도록 연습하자.

 

문제

두 수의 합 문제는 다음과 같다.

n개의 정수로 이루어진 수열이 입력되었을 때, 서로 다른 위치의 두 수를 뽑아 더한 값이 k가 되는 경우의 수를 구하는 문제이다.

 

풀이

모든 두 수 조합을 비교하는 것은 매우 시간이 오래 걸린다.

딕셔너리에 중복 값을 넣어주고, 중복 값을 제외한 뒤 비교하는 것도 마찬가지로 시간이 오래 걸린다.

5달 전에도 같은 문제를 풀었는데 습관처럼 위와 같은 방법을 사용했었다.

하지만 앞의 숫자부터 k값을 만들 수 있는 짝꿍이 있는지 비교하면서 경우의 수를 세어주는 것이 가장 빠른 방법이다.

이번엔 머릿속에 꼭 넣어두자.

 

코드

n,k = map(int,input().split())
arr = list(map(int, input().split()))

numb = dict()
cnt = 0

for i in range(n):
    # 현재 값과 짝꿍이 될 수 있는 값을 말한다.
    diff = k - arr[i] 
    
    # 짝꿍이 될 수 있는 값이 이미 딕셔너리에 추가되어 있다면 
    # 현재 값과 짝꿍이 될 후보가 그 수만큼 있다는 뜻이다.
    # 즉 그 수만큼 경우의 수가 증가하면 된다.
    if diff in numb:  
        cnt += numb[diff]
    
    # 현재 값은 다른 숫자들의 짝꿍 후보가 될 수 있기에
    # 딕셔너리에 현재 값을 넣어준다.
    # 이미 같은 값이 존재한다면 개수를 늘려주면 된다.
    if arr[i] in numb:
        numb[arr[i]] += 1
    else:
        numb[arr[i]] = 1

# 마지막 경우의 수를 출력한다.
print(cnt)

 

 

https://www.codetree.ai/landing/level-test/5888/result/4?&utm_source=clipboard&utm_medium=text 

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