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

문제 설명

 

dfs개념 활용

dfs = 깊이우선탐색

하나의 노드를 다 돈 후에 마지막에 실행된 스택을 지우고 인접한 상위 노드를 방문한다.

이 문제의 예로 보자면 +를 다돈 후 +트리의 마지막 부터 -로 갈라짐 또 - 에는 +와 -가 있음.

 

ex)

+++++

++++-

+++-+

+++--

.

.

 

---

문제 풀이

function solution(numbers, target) {
    let answer = 0
    
    dfs(0,0)
    
    function dfs (index,sum) {
        if(index === numbers.length) {
            if(sum === target) {
                answer++
            }
            return
        }
    dfs(index+1,sum+numbers[index])
    dfs(index+1,sum-numbers[index])
    }
    
    return answer
}

1. dfs 기본값 지정

 

2. numbers배열의 요소들을 차례대로 더해줘야 하기에 index와 sum을 매개변수로 하는 재귀함수 설정

 

3. index가 numbers.length와 같다면 (배열의 끝까지 더해준 상태)

 

4. 그 때 sum이 target값과 같다면 answer를 1씩 더해준다.

 

5. 함수의 실행 부분은 더해주는 함수와 빼주는 함수 (1번함수가 실행이 다된 후 dfs 개념에 따라 조금씩 2번함수가 실행)

---

배운 점

dfs의 개념과 사용법 => 재귀함수가 핵심