[Programmers] 깊이/너비 우선 탐색 > 타겟 넘버

이번에는 깊이/너비 우선 탐색 문제를 풀어보겠습니다.

[Programmers] 깊이/너비 우선 탐색 > 타겟 넘버

출처 : 프로그래머스

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

문제 풀이

리스트를 사용해서 각각 차례대로 numbers에서 주어진 숫자를 빼고 더해주며 리스트를 최신화 했습니다. 그리고 난 후 모든 과정이 끝났을 때 리스트의 들어있는 숫자들을 target과 비교하여 answer를 구했습니다.

def solution(numbers, target):
    
    answer = 0
    
    prev_list = [-numbers[0], numbers[0]]
    
    for i in range(1, len(numbers)):
        next_list = []
        for v in prev_list:
            num = v
            next_list.append(num-numbers[i])
            next_list.append(num+numbers[i])
            
        prev_list = next_list
    
    for k in prev_list:
        if k == target:
            answer += 1
            
    return answer

테스트 결과

다른 사람들의 풀이

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])

재귀함수를 사용해서 풀어준 모습이 보입니다.

결과를 비교하면 두 코드 모두 정확성 부분에서는 똑같으나 코드를 수행하는 시간과 메모리에서 차이가 나고 있습니다.