[프로그래머스] [Python] Level2_타겟 넘버

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

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

1차 시도 - Stack

def solution(numbers, target):
    answer = 0
    stack = [[numbers[0],0], [-1*numbers[0],0]] #[value, idx]
    
    n = len(numbers)
    while stack:
        temp, idx = stack.pop() #target
        idx += 1 #다음거에
        if idx < n: #child를 넣는다
            stack.append([temp+numbers[idx], idx])
            stack.append([temp-numbers[idx], idx])
        else:
            if temp == target: answer += 1 #child를 끝까지 넣었으면 그 끝에 계산된 값이 나오니까 그게 target인지 검사
    return answer

2차 시도 - Recursion

def solution(numbers, target):
    n = len(numbers)
    answer = 0
    
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal answer
                answer += 1
            return
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
            
    dfs(0,0)
    return answer

 

💡최종로직