[프로그래머스] 자바스크립트 '타겟 넘버' 문제 풀이 (LV.2)

프로그래머스 자바스크립트 타겟 넘버 문제 풀이

📖 들어가며

DFS 깊이 우선 탐색 알고리즘을 사용하는 프로그래머스 '타겟 넘버' 문제 풀이를 해보겠다.

❓ 문제 

문제 설명

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 함수를 작성해주세요.

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	retrun
[1,1,1,1,1]	3	5
[4,1,2,1]	4	2

입출력 예 설명

예제 #1
문제 예시와 같습니다.

예제 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

💡 풀이

코드

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

  function dfs(count, sum) {
    if (count === length) {
      if (target === sum) {
        answer++;
      }
      return;
    }

    dfs(count + 1, sum + numbers[count]);
    dfs(count + 1, sum - numbers[count]);
  }

  dfs(0, 0);

  return answer;
}

기본적인 DFS 문제다.

배열 [1, 2, 3]로 예를 하나 더 들어보면 

1 + 2 + 3인 경우, 1 + 2 - 3인 경우, 1 - 2 + 3인 경우, 1 - 2 - 3인 경우. 모든 경우의 수의 결과 값을 찾아서 target 넘버와 같은 개수를 찾는 문제다.

 

재귀 함수를 호출할 때 중단 점을 지정해 줄 count 인수와 숫자들의 합을 넘겨줄 sum 인수 총 두 가지 인수를 지정해주도록했다.

count가 for문에서 index 역할을 한다고 생각하면 된다.

 

매개변수로 넘어온 count는 numbers 배열의 길이랑 같아지고, 그때 target과 sum의 값이 같다면 answer의 값을 증가시키고 현재 함수를 종료시키도록 했다.

 

하지만, 위 경우가 아니라면

다시 dfs함수에 count를 + 1 증가시키고, 연산자 '+'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내 합을 계산한 값을 인수로 주고,

'+'를 계산한 함수가 끝났다면 연산자 '-'를 계산할 수 있도록 sum과 numbers의 숫자 하나를 꺼내서 차이를 계산한 값을 인수로 주었다.

 

예제#2를 예시로 대략의 트리를 그려보았다.

+를 하는 dfs함수는 왼쪽으로 뻗고, -를 하는 dfs함수는 오른쪽으로 뻗어서 밑에서부터 탐색하게 된다.

예제 2 트리

✔ 채점

채점 결과