타겟 넘버

문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

 

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

1. -1+1+1+1+1 = 3

2. +1-1+1+1+1 = 3

3. +1+1-1+1+1 = 3

4. +1+1+1-1+1 = 3

5. +1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타켓 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return하도록 solution 함수를 작성해주세요.

 

· 제한사항

1. 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.

2. 각 숫자는 1이상 50이하인 자연수입니다.

3. 타겟 넘버는 1이상 1000이하인 자연수입니다.

 

· 입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

---

풀이

1. Me

1) 1차 시도

from itertools import permutations

def solution(numbers, target):
    number_list = numbers.copy()
    for i in numbers:
        minus_val = (0 - i)
        number_list.append(minus_val)
    
    print(number_list, numbers)
    val = set(tuple(permutations(number_list, len(numbers))))
    count = 0
    for i in val:
        if sum(i) == target:
            count += 1 
    print(len(val))

solution([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 3)

-> 이렇게 풀었더니 답은 맞게 나오는데, 엄청난 시간이 소모된다. 입력받은 숫자의 개수가 20개일 때, 40개의 배열을 만들고 여기서 20개의 조합을 만들면 엄청난 시간이 안 걸리는게 이상할 수 밖에 .. 

 

2) 2차 시도

def solution(numbers, target):
    result = []
    def dfs(c_calc, numbers, index, path):
        if len(path) == len(numbers):
            if c_calc == target:
                result.append(path)
                return 
            else:
                return 
        for i in range(index, len(numbers)):
            dfs(c_calc+numbers[i], numbers, i+1, path + [numbers[i]])
            dfs(c_calc-numbers[i], numbers, i+1, path + [-numbers[i]])
        
    dfs(0,numbers, 0, [])
    return len(result)

-> dfs를 통해 완전 탐색을 구현하여 문제를 풀었다. 정답은 모두 맞췄지만, 테스트케이스 1, 2번 문제에서 시간초과로 통과못했다.

 

3) 3차 시도

def solution(numbers, target):
    result = []
    def dfs(c_calc, numbers, index, path):
        if len(path) == len(numbers):
            if c_calc == target:
                result.append(path)
                return 
            else:
                return 
 
        dfs(c_calc+numbers[index], numbers, index+1, path + [numbers[index]])
        dfs(c_calc-numbers[index], numbers, index+1, path + [-numbers[index]])
        
    dfs(0,numbers, 0, [])
    return len(result)

2차 시도의 for문을 제거하고, 그냥 dfs 호출을 통해 문제를 풀었다. 계산한 값이 target과 같고, path의 길이가 입력받은 배열의 길이와 같으면 dfs 호출을 종료하도록 구현하였다. 앞선 시도에서 시간초과가 발생한 이유는 for문을 엄청나게 많이 수행했기 때문인 것으로 보이며, 해당 문제는 생각해보니 조합 문제가 아니기 때문에 for문을 사용하지 않고 풀 수 있었다.

 

2. Others

1) DFS (재귀호출)를 이용한 풀이

def dfs(nums, i, n, t):
    ret = 0
    if i==len(nums):
        if n==t: return 1
        else: return 0
    ret += dfs(nums, i+1, n+nums[i], t)
    ret += dfs(nums, i+1, n-nums[i], t)
    return ret

def solution(numbers, target):
    answer = dfs(numbers, 0, 0, target)
    return answer

ret 변수를 사용하여 합계가 target이고, index 값이 nums 배열의 길이와 같은 경우 +1씩 증가시켰다.

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer

global 변수를 사용하여 문제를 풀었다.

 

2) DFS (스택)를 이용한 풀이

def solution(numbers, target):
    q = [0]
    for n in numbers:
        s = []
        for _ in range(len(q)):
            x = q.pop()
            s.append(x + n)
            s.append(x + n*(-1))
        q = s.copy()
    return q.count(target)

3) Python 답게 푸는 방법

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

4) 재귀 마술사

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])