[프로그래머스] 타겟 넘버 - 파이썬(python)

 

 

나의 풀이

a = 0

def dfs(i, result, numbers, target) :
    global a
    if i == len(numbers) :
        if result == target : 
            a+=1
            return
    else :
        dfs(i+1, result+numbers[i], numbers, target)
        dfs(i+1, result-numbers[i], numbers, target)

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

 

위 그림처럼 i번째 숫자에 대해 +부호 or -부호를 붙여 계산하는 모든 경우의 수를 따져보면 된다.

즉, DFS 로 모든 경우에 대해 깊이 우선 탐색을 한다.

그리고, i가 마지막원소일 때 최종 합이 target 과 같다면, 전역변수 a의 값을 1 증가시킨다.

 

 

다른 풀이

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)

재귀함수 대신 스택을 사용한 풀이이다.

count 함수를 사용한 것이 인상적이다.