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

문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

의식의 흐름

DFS, BFS를 어떻게 구현하지?
재귀함수를 써보자
어떻게 쓰지? -> map으로 돌리면서 하면 되지 않을까? -> 실패

다른이의 정답

참조 : 블로그

function solution(numbers, target) {
    var answer = 0;
  // 처음 시작은 개수 0개, 합계 0 으로 시작하면서 모든 경우를 dfs로 탐색
    recur(0, 0);
    return answer;

    function recur(count, sum){
      // leaf node 도착했을 때, 모든 numbers 탐색
        if( count === numbers.length){
          // 주어진 조건에 만족하면 answer++
            if(sum ===target ){
                answer++
            }
          // 리턴해주어야함
            return
        }

      // left child 는 +일 경우
        recur(count+1, sum+numbers[count]);
      // right child 는 -일 경우
        recur(count+1, sum-numbers[count]);
    }
}

 

주석 없앤 코드

function solution(numbers, target) {
    var answer = 0;
    function re ( idx,sum){
        if ( idx == numbers.length){
            if (sum == target){
                answer += 1
            }
            return
        }

        re (idx+1,sum+numbers[idx])
        re (idx+1,sum-numbers[idx])
    }
    re(0,0)
    return answer
}

DFS(깊이 우선 탐색)을 이용한 풀이다.
이를 이해하기 위해서 node 개념을 확실히 알아야됐다.
처음봤을때 재귀함수를 돌리는데 이게 어떻게 전부 탐색되는거지?
첫번째 재귀함수에서 +만 하니까 +5까지 그냥 가는거 아닌가 싶었는데, 그렇게 보지말고, 하나의 node에서 +한번(첫번째 재귀함수), -한번(두번째 재귀함수) 을 수행한다는 개념으로 보니까 이해가 됐다.

각 node별로 +한번 -한번씩 해보면서 idx == numbers.length 만큼, 즉 전체 배열의 길이 됐을때만 결과를 보고 만족하면 카운팅 한다는 거였다.

 

이렇게 되면 각 node에서 +,-했을때를 전부 계산한거니, 모든 경우의 수를 따져본게 된다.