1253. 좋다 (Python)

1253번: 좋다

 

풀이

 입력으로 주어진 수가 총 몇 개 있는지 딕셔너리를 이용하여 기록한다. 2중 for문을 통해서 모든 수를 더한 경우를 구하고 두 수를 더한 수가 몇 개 있는지를 딕셔너리를 통해서 체크한다. 두 수의 합은 다음과 같이 3가지 경우가 존재한다.

 

1. 두 수를 합한 값이 두 수와 모두 같은 경우 (ex. 0 + 0 = 0)
    이런 경우는 두 수가 모두 0일 때만 존재한다. 0이 좋은 수가 되기 위해서는 리스트에 0이 3개 이상 존재해야 한다. 
    0, 0 2개만 존재할 경우 두 수를 합한 0이 다른 인덱스에 존재하지 않으므로 0은 좋은 수가 될 수 없다. 만약 0, 0, 0과 같이 3개 이상 존재하면 0은 좋은 수가 될 수 있다. 
     
    위와 같이 0, 0, 0이 리스트로 주어지면 좋은 수는 총 3개가 된다. 
   (1) 첫 번째 0 + 두 번째 0 = 세 번째 0
   (2) 첫 번째 0 + 세 번째 0 = 두 번째 0 
   (3) 두 번째 0 + 세 번째 0 = 첫 번째 0 
   
    그렇기 때문에 결과값에 0이 있는 개수만큼을 더해 주고 딕셔너리에서 0의 개수를 0으로 초기화 해준다. 
   
   
2. 두 수를 합한 값이 하나의 수와 같은 경우 (ex. 0 + 1 = 1)
    하나의 수가 0일 때 발생한다. 리스트가 0, 1로 주어지면 0 + 1 = 1이 되지만 덧셈에 사용된 1을 제외한 다른 1이 존재하지 않기 때문에 1은 좋은 수가 될 수 없다.
   
    리스트가 0, 1, 1로 주어지면 1은 좋은 수가 될 수 있다. 
   (1) 0 + 첫 번째 1 = 두 번째 1
   (2) 0 + 두 번째 1 = 첫 번째 1 
   
    결과값에 1이 있는 개수만큼을 더해 주고 딕셔너리에서 1의 개수를 0으로 초기화 해준다. 
   
   
3. 두 수를 합한 값이 두 수와 다른 경우 (ex. 1 + 2 = 3)
    일반적인 경우로 합한 값이 1개 이상일 때 좋은 수를 발견할 수 있다. 위의 경우들과 마찬가지로 결과값에 합한 수의 개수만큼을 더해 주고 딕셔너리에서 해당 합한 수의 개수를 0으로 초기화 해준다.
   
   

코드

from collections import defaultdict

if __name__ == '__main__':
    N = int(input())
    nums = list(map(int, input().split()))

    # 각 숫자가 총 몇 개 있는지 기록하기 위한 딕셔너리
    numDict = defaultdict(int) 

    for num in nums:
        numDict[num] += 1

    cnt = 0 # 좋은 수의 개수 

    for i in range(N):
        for j in range(i+1, N):
            tmp = nums[i] + nums[j]

            if tmp == nums[i] and tmp == nums[j]: # 두 수가 모두 합한 수와 같을 때 (ex. 0 + 0 = 0)
                if numDict[tmp] > 2: # tmp가 3개 이상일 때 좋은 수를 발견할 수 있다.
                    cnt += numDict[tmp]
                    numDict[tmp] = 0
            elif tmp == nums[i] or tmp == nums[j]: # 두 수중 하나의 수가 합한 수와 같을 때 (ex. 0 + 3 = 0)
                if numDict[tmp] > 1: # tmp가 2개 이상일 때 좋은 수를 발견할 수 있다.
                    cnt += numDict[tmp]
                    numDict[tmp] = 0
            else: # 두 수가 합한 수와 모두 다를 때 (ex. 1 + 2 = 3)
                if numDict[tmp] != 0: # tmp가 1개 이상일 때 좋은 수를 발견할 수 있다.
                    cnt += numDict[tmp]
                    numDict[tmp] = 0

    print(cnt)