43. Target Sum

문제

nums 배열과 target을 인수로 받는다.

배열의 각 요소 앞에 +나 -를 붙여서 수식을 만들었을 때, 계산하면 target이 나오는 수식의 개수를 구하시오. 

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

 

해결 방식

* Counter : 리스트의 원소 개수를 세어서 딕셔너리에 담아줌. 

from collections import Counter

arr = [1, 1, 2, 2, 2]
result = Counter(arr)
print(result)
# Counter({2: 3, 1: 2})

nums를 iterate 하면서

1) step 딕셔너리에 현재 num에서 나올 수 있는 합을 모두 저장 

2) result 딕셔너리를 step 딕셔너리로 업데이트 

from collections import Counter  

def findTargetSumWays(nums, target):
  # nums의 첫 요소에 +, -를 붙인 것이 1개로 카운트되게 세팅
  result = Counter({0:1})
  
  for num in nums:
    step = Counter()
    # count 딕셔너리에 들어있는 값을 iterate
    for key in result:
      step[key + num] += result[key]
      step[key - num] += result[key]
      
    result = step

  return result[target]

nums가 [20, 30]이고 target이 90인 경우

0번째(num이 20일 때) iteration 후 result는 {20 : 1, -20: 1}

1번째(num이 30일 때) iteration 후 result는 {50 : 1, -10: 1, 10:1, -50:1}

iteration 완료 후 result에서 키가 target인 요소의 값 반환.