[프로그래머스][python] 타겟넘버 - DFS/BruteForce

문제

• 프로그래머스 타겟넘버
• Level 2
• Link

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

 

나의 접근

1. Brute Force

우선 완전 탐색으로 풀어보았다. 주어지는 숫자의 개수가 최대 20개다보니 시간 초과가 뜨지 않고 모든 테케가 통과된다. 

# Brute Force 
def solution(numbers, target):
    answer = 0
    current_list = [numbers[0], -numbers[0]]

    for i in range(1, len(numbers)):
        next_number = numbers[i]
        next_list = []
        for num in current_list:
            next_list.append(num + next_number)
            next_list.append(num - next_number)

        current_list = next_list

    for num in current_list:
        if num == target:
            answer += 1
    return answer

 

2. DFS

하지만? 완전탐색으로 풀게 되면 numbers 개수가 아주 커지면 시간초과가 뜰 확률이 크다. 그리고 위의 접근법은 모든 정답을 계속해서 저장해나가기 때문에 메모리 면에서도 효율적이지 않다. 따라서 DFS로 다시 풀어보았다.

1. 재귀를 한 번씩 돌려줄 때마다 level에 저장, 현재 숫자에 그 다음 숫자를 더해주거나 빼준다.
2. Level이 1일 경우(첫 번째 원소인 경우)에는
   1. [+1 +1 +1 +1 +1] 이런식으로 수 앞에 기호가 놓이기 때문에 num이 +1일 경우와 -1일 경우에 대해서 재귀를 수행해주어야 한다.
3. Level이 numbers의 길이와 같아지면, 결과를 target number와 비교하고 result를 +1 해준다.

# DFS Approach
def solution(numbers, target):
    result = 0
    def dfs(num, level):
        nonlocal result

        if level == len(numbers):
            if num == target:
                result += 1
            return
        
        signs = [-num, num]
        if level == 1:
            for i in range(2):
                dfs(signs[i] + numbers[level], level + 1)
                dfs(signs[i] - numbers[level], level + 1)
        else:
            dfs(num + numbers[level], level + 1)
            dfs(num - numbers[level], level + 1)
                
    dfs(numbers[0], 1)
    return result