[프로그래머스 Lv.2] 타겟넘버

 

✅ 재귀 풀이 

answer=0

def dfs(numbers,target,cur_idx,cur_total):
    global  answer

    # 탈출 조건(모든 수 순회)
    if cur_idx==len(numbers):
        if cur_total==target:
            answer+=1
        return

    else:
        dfs(numbers,target,cur_idx+1,cur_total+numbers[cur_idx])
        dfs(numbers,target,cur_idx+1,cur_total-numbers[cur_idx])


def solution(numbers, target):
    global answer
    dfs(numbers,target,0,0)

    return answer

answer를 전역변수로 사용해서, dfs함수 내에서 타겟넘버를 찾았을때 카운트를 증가시켜주고 solution함수 내에선 이 값을 리턴해주는 방식으로 하였다.

주어진 numbers의 수를 순회하면서 +/-  연산을 수행하면서, 모든 수를 순회하면 타겟넘버와 일치하는지 여부를 확인하고, 카운트해준뒤 재귀를 탈출해준다. 

+와 - 연산을 둘다 해줘야하기 때문에, 2번의 재귀호출을 해주며, 순회는 현재 idx+1씩 해주고, 누적값을 재귀호출할때마다 넘겨준다.

 

def solution(numbers, target):
    answer=0

    def dfs(cur_idx,cur_total):
        nonlocal answer
        if cur_idx==len(numbers):
            if cur_total==target:
                answer+=1
            return

        dfs(cur_idx+1,cur_total+numbers[cur_idx])
        dfs(cur_idx+1,cur_total-numbers[cur_idx])

    dfs(0,0)

    return answer

 

 

✅ 스택 풀이

def solution(numbers, target):
    answer=0
    stack=[(0,0)] #(현재idx,누적합)
    while stack:
        idx,total=stack.pop()

        if idx==len(numbers):
            if total==target:
                answer+=1
            continue

        stack.append((idx+1,total+numbers[idx]))
        stack.append((idx+1,total-numbers[idx]))

    return answer

콜스택의 제한이 있기 때문에, limit을 늘릴순 있지만 이 방법은 좋은 풀이는 아니라는 의견을 들었던 기억이 있어, 이 문제는 재귀로 풀이가 가능하지만, 스택을 이용해서도 풀어보았다. 

재귀가 아니므로 리턴대신, 다음 반복 턴으로 넘기기 위해 continue를 사용해주었다.

 

 

 

 

✅ JS 풀이

function solution(numbers, target) {
    var answer = 0;
    
    function dfs(idx,sum){
        if(idx<numbers.length){ //numbers의 첫번째부터 마지막까지 
           dfs(idx+1,sum+numbers[idx])  //+(left)
            dfs(idx+1,sum-numbers[idx]) //-(right)
        }
          else{ //leaf에 도달
           if(sum===target){ //target 찾음
                answer++;
            }   
          } 
        
    }
    
    dfs(0,0)
    return answer;
}