프로그래머스 Level 2 타켓 넘버

간단한 DFS, BFS 문제이다. DFS, BFS를 안 사용하고도 풀어봤다.

 

DFS 풀이

def dfs(n, numbers, target, i):
    if i == len(numbers):
        return 1 if n == target else 0
    return dfs(n + numbers[i], numbers, target, i+1) + dfs(n - numbers[i], numbers, target, i+1)

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

생각해보니 굳이 dfs 함수를 만들 필요도 없었다.

아래와 같은 방식으로 numbers 리스트의 앞에 값을 빼가면서, target이 0이 되는지 확인하는 방법도 있다.

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

 

BFS 풀이

from collections import deque

def solution(numbers, target):
    q = deque([(0, 0)])
    ans = 0

    while q:
        n, i = q.popleft()
        if i == len(numbers):
            if n == target:
                ans += 1
        else:
            q.append([n + numbers[i], i+1])                
            q.append([n - numbers[i], i+1])                
        
    return ans

 

풀이 DFS, BFS 사용 X

def solution(numbers, target):
    res_li = [0]
    for n in numbers:
        li = []
        for res in res_li:
            li.append(res + n)
            li.append(res - n)
        res_li = li
    
    return res_li.count(target)