[LeetCode] 494. Target Sum (Python)

 

난이도: Medium

 

문제 설명

---

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

Return the number of different expressions that you can build, which evaluates to target.

 

문제 예제

---

Example 1:

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

Example 2:

Input: nums = [1], target = 1
Output: 1

 

제한사항

---

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• 1000 <= target <= 1000

 

✏️ Solution(솔루션)

---

class Solution:  
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)

        if n == 1:
            if abs(target) == abs(nums[0]):
                return 1
            else:
                return 0

        answer = 0
        set_list = [set() for i in range(n)]
        set_list[0].add(nums[0])
        count = [defaultdict(int) for i in range(n)]

        for i in range(1, n):
            for j in set_list[i-1]:
                if count[i-1][j] > 0:
                    count[i][j+nums[i]] += count[i-1][j]
                    count[i][j-nums[i]] += count[i-1][j]
                else:
                    count[i][j+nums[i]] += 1
                    count[i][j-nums[i]] += 1
                set_list[i].add(j + nums[i])
                set_list[i].add(j - nums[i])

        return count[-1][target] + count[-1][-target]

 

 

처음에는 다음과 같이 백트래킹 방법으로 접근하여 풀었지만, 시간초과가 나는 것을 확인했다.

answer = 0

def recursion(now_sum, now, nums, target, n):
    global answer

    if now == n:
        if now_sum == target:
            answer += 1
        return
    
    recursion(now_sum + nums[now], now+1, nums, target, n)
    recursion(now_sum - nums[now], now+1, nums, target, n)
    
class Solution:  
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        global answer
        answer = 0

        recursion(0, 0, nums, target, len(nums))
        
        return answer

 

그래서 모든 경우의 수에 대해 연산하기 위해 리스트를 만들어 수행해봤지만 리스트가 2^20 이상 크기로 만들어져 역시 시간초과가 일어났다.

 

그러다가 눈에 보인 것이 같은 연산이 많이 일어난다는것이었다.

 

예를들어 nums = [1,1,1] 이라고 했을 때

+1+1 = 2 

+1-1 = 1

-1+1 = 1

-1-1 = 0

 

위와 같이 +1-1과 -1+1은 1로 결과가 똑같다.

따라서 이 다음에 일어날 연산은 하나만 해도 결과를 확인할 수 있다는 뜻이다.

 

그래서 set을 통해 연산할 숫자의 중복을 없앴다.

예를들어, nums = [1,1,1,1,1]이라고 했을 때, 각각 -와 + 부호를 붙였을 때 결과는 다음과 같이 저장된다.

 

원래대로라면 각 i번째의 2^i 길이의 배열이 와야하지만 set을 통해 중복이 사라져 그 길이가 많이 줄어든 것을 확인할 수 있다.

 

이렇게만 했을 때, 연산이 많이 줄어든 것은 좋은데 target의 수를 확인할 수 없다는 것이다.

그래서 dictionary를 담고있는 count 리스트를 만들었다.

 

위 그림에서 {1,3,-1}에 해당하는 dictionary를 확인해보면 다음과 같다.

 

set에서는 1이 하나지만 딕셔너리에는 2개로 저장되어 있는 모습을 확인할 수 있다.

 

이제 다음 num으로 넘어가서 만약 1로 연산을 하면 그다음 count에는 +1을 하는 것이 아닌 +2로 저장하는 것이다.

 

이런식으로 nums의 끝까지 진행한다.

 

모든 연산이 끝나면 target의 갯수를 반환하면 된다.

또한, 이 연산은 첫번째가 무조건 +부호로 시작하기 때문에 target 갯수뿐만 아니라 -target 갯수를 더해 정답을 return하였다.

---

494. Target Sum (Python)