programmers 타겟넘버(DFS/BFS)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

위 문제는 numbers에 있는 모든 숫자를 이용하여 target을 만드는 경우의 수를 구하는 문제인데, +와 -연산자만 이용하여 경우의 수를 구하여야 한다.

 

나의 경우 dfs를 사용하여 풀이를 하였는데,

numbers의 모든 숫자를 순회하기 위해 dfs의 매개변수로 인덱스(나의 경우 level)을 재귀할 때 마다 키워주었고, Sum이란 매개변수로 연산을 하여 target과 맞는 숫자가 있는지 확인하였다.

---

def solution(numbers, target):
    answer = 0
    arr = ['-', '+']

    def dfs(level, Sum):
        nonlocal answer  # 전역에 설정된 변수가 아니므로 global이 아닌 nonlocal을 이용한다.
        if level == len(numbers):
            if Sum == target:
                answer += 1
            return

        for i in range(2):
            if arr[i] == '-':
                dfs(level + 1, Sum - numbers[level])

            if arr[i] == '+':
                dfs(level + 1, Sum + numbers[level])


    dfs(0, 0)

    return answer

프로그래머스를 자주 이용하지 않는 사람들은 입출력문제로 골치 아플 수 있음;;