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

타겟 넘버
트리에 대해서 공부를 했으니 트리에 관련된 문제를 풀어보았다.

이 문제는 주어진 배열 요소를 하나씩 더하거나 빼서 최종적으로 target과 같은 값이 되는 경우의 수를 찾는 문제이다. '경우의 수'에서 알 수 있다시피 DFS를 통해서 해결을 할 수 있는 문제다. DFS를 구현하는 방법은 스택이 있고, 이번에는 재귀를 사용했다.

시간 복잡도는 leaf node의 갯수 만큼이기 때문에 O(2^배열의 길이)이다. 아래는 배열[1, 2]이 주어질 때 해당 노드에 대해 문제와 같은 조건으로 트리를 그려보았다.

배열의 길이가 2기 때문에 leaf node가 2의 제곱인 것을 알 수 있다.

function solution(numbers, target) {
  let answer = 0;
  const length = numbers.length;

  const DFS = (count, sum) => {
    if (count === length) {
      if (sum === target) answer++;
      return;
    }
    DFS(count + 1, sum + numbers[count]);
    DFS(count + 1, sum - numbers[count]);
  };

  DFS(0,0);
  return answer;
}

함수 DFS를 재귀적으로 호출하면서 다음 요소를 더하고 빼면서 호출한다. 배열의 길이 만큼 호출이 됐고 그 합의 결과가 target과 동일하다면 카운트를 해준다.