[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 타겟 넘버

📌  문제

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	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

---

📌  풀이

알아야 하는 것

• 재귀함수

구할 것

예컨대 배열 [1, 1, 1, 1, 1]로 3을 만들 때, 1+1+1+1-1 로도 만들 수 있고 1+1+1-1+1로도 만들 수 있다. 재귀함수를 통해 -1과 +1의 자리를 바꿔가면서 합을 더하며 배열을 순회하되 배열을 전부 순회했을 때 합이 타겟 넘버라면 answer +1 을 해준다.

 

재귀함수의 종료 조건은 인덱스가 배열의 길이와 같을 때다.

 

예시에서 3을 만든 5가지 방법을 보여줘서 몰랐는데, 저렇게 여러 번 자리를 바꿔가면서 했을 때 3이 나온 부분만 잘라낸거라는 생각이 들었다. 1+1+1+1+1 로 가면 배열의 길이까지 갔지만 합계가 5로 타겟 넘버인 3보다 크기 때문에 재귀로 -1을 했을 때로 돌아간다.

 

그러면 1+1+1+1-1이 되는데 이 때는 합계가 타겟 넘버와 같기 때문에 answer +1 이 된다.

다음으로 인덱스가 배열보다 길어지니 다시 뒤로 돌아오면 1+1+1-1+1로 또 answer +1 이 되고... 이런 식으로 돌아간다. 

 

예시가 1이라서 -1과 +1의 자리인거지 문제 풀이로 쓰면 합계 + numbers[idx], 합계 - numbers[idx]로 인덱스에 해당하는 요소 값만큼 더해주고 빼주는 것이다. 생각보다 엄청 어려운 문제는 아니었고 오히려 [1, 1, 1, 1, 1]을 한번 쓱 따라 해보다가 생각났다.

 

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

  function dfs(idx, sum) {
    if (idx === numbers.length) {
      if (sum === target) {
        answer += 1;
      }
    } else {
      dfs(idx + 1, sum + numbers[idx]);
      dfs(idx + 1, sum - numbers[idx]);
    }
  }

  dfs(0, 0);
  return answer;
}

 

**참고

이 분이 그림으로 풀이해놓으신 게 참 좋은 듯. 이렇게 트리가 확장되는 개념이라고 생각하면 보다 직관적으로 이해할 수 있다.

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