[프로그래머스] 타겟 넘버 (자바스크립트/javascript/js)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

문제 풀기 위한 아이디어

주어진 numbers의 숫자들을 더하거나 빼야하므로 예제를 그림으로 나타내면 다음과 같다.

예제에서는 숫자가 5개 였지만 depth를 5까지 그림으로 표현하기에는 너무 가독성이 떨어져서 4 depth까지만 표현했다.

이렇게 numbers라는 배열에 들은 각각의 값들은 +이거나 - 인 경우를 가지고 있고, 이 모든 경우의 수를 DFS로 탐색하면 된다. 이 문제는 BFS로는 아마 풀 수 없을 것이라고 확신한다. 이 모든 노드를 탐색해야하는 것이 아니라 depth에 따라 경로만 탐색하면 되기 때문이다.

DFS로 풀어야한다는 감은 잡았지만 코드를 어떻게 구현해야할지 고민을 하는데에 시간이 걸렸다.

그러나 BFS나 DFS 모두 틀에 구현받지 않고 BFS는 큐로 구현하고 DFS는 재귀함수를 통해 구현한다는 포인트만 기억하면 문제에 따라 그 때 그 때 풀면 어느정도 풀리는 것 같다.

내가 구현한 코드 (자바스크립트)

function solution(numbers, target) {
  const DFS = (sum, level, array) => {
    if (level === numbers.length - 1) {
      if (sum === target) {
        answer.push(array);
      }
      return;
    }
    DFS(sum + numbers[level + 1], level + 1, [...array, numbers[level + 1]]);
    DFS(sum - numbers[level + 1], level + 1, [...array, -numbers[level + 1]]);
  };
  const answer = [];
  DFS(numbers[0], 0, [numbers[0]]);
  DFS(-numbers[0], 0, [-numbers[0]]);

  return answer.length;
}
const numbers = [1, 1, 1, 1, 1];
const target = 1;
console.log(solution(numbers, target));

우선 DFS 함수를 만든다. 이 함수는 sum, level, array를 인자로 받는 함수이다.
이 문제에서는 가능한 경우의 수만 출력하면 되므로 사실 DFS 함수 안에서 array 인자를 받을 필요가 없지만 개인적으로 어떤 경우의 수로 나왔는지 확인하기 위해서 array를 추가했다.

DFS함수에서는 level을 증가시키며 DFS를 재귀적으로 실행시킨다. 재귀함수는 반복문과 마찬가지로 반드시 종료 조건이 있어야 하는데, level이 numbers의 길이-1 일 때 종료가 된다. 이 때 target과 sum이 같다면 정답에 추가하면 된다.