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

문제 링크

프로그래머스

 

문제 유형

DFS/BFS

 

문제 풀이

이번 문제는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 주어지고 배열 내의 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 리턴하는 문제이다. 해당 문제는 recursive DFS를 구현하여 해결할 수 있다. 0번 인덱스부터 dfs 함수를 호출하여 마지막 인덱스까지 모든 숫자를 더한 값을 계산하고 계산한 결과가 타겟 넘버인지를 확인한다. 마지막 인덱스까지 확인 후 재귀를 빠져나와 숫자가 음수인 경우를 탐색한다.

 

코드

function solution(numbers, target) {
    let answer = 0;
    
    function dfs(idx, sum) {
        // 종료 조건
        if (idx === numbers.length) {
            if (sum === target) {
                answer++;
            }
            return;
        }
        
        dfs(idx + 1, sum + numbers[idx]);
        dfs(idx + 1, sum - numbers[idx]);
    }
    
    dfs(0, 0);
    return answer;
}

 

참고

https://jjnooys.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-javascript-1d7983d423b5

[프로그래머스] 타겟 넘버 (javascript)