[Programmers]深度/幅優先ナビゲーション>ターゲット番号

今回は,まず深さ/幅ナビゲーションの問題を解く.

[Programmers]深度/幅優先ナビゲーション>ターゲット番号

ソース:プログラマ
https://programmers.co.kr/learn/courses/30/lessons/43165

問題を解く

リストを使用して、指定した数値を数値から減算し、リストの最新部分に追加します.次に、すべてのプロセスが終了した後、リストの数字をtargetと比較して、答えを求めます.

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

再帰関数を使用して解放された結果を示した.

比較の結果,両コードは正確性は同じであったが,コードを実行する時間とメモリに差があった.