타켓 넘버

문제설명

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

문제풀이

numbers 배열의 각 숫자의 앞에 +, - 둘 중 하나만 붙일 수 있습니다. 문제 설명의 예시를 갖고 이진트리로 생각을 해보면

      1
   +/    \-
   1	  1
 +/  \- +/  \-
 1    1 1    1 
 ...

이런식으로 배열을 순회하며 각 요소에 +, -를 붙인 모든 경우의 수를 계산해보았을 때 배열의 마지막 요소에 +, -를 붙여서 계산해보았을 때 target과 같다면 정답을 하나 추가합니다.
이것을 구현하기 위해 재귀함수를 활용했습니다.

 DFS(answer, index, numbers, target)

index를 체크해서 마지막 요소까지 +, -를 붙인 answer라면 target과 비교하여 정답인지 확인합니다.

 if(index == numbers.length){
   if(answer == target) return 1
   else return 0
 }

마지막 요소가 아니라면, 현재 index에 +, -를 붙인 재귀함수를 호출합니다.

 return DFS(answer+numbers[index], index+1, numbers, target) + 
            DFS(answer-numbers[index], index+1, numbers, target)

다른사람의 코드를 보고 배운 점

코드 간략화

DFS함수의 같은 값인 파라메터 numbers, target을 solution 함수 내부에서 DFS함수를 구현하면 파라메터 numbers, target을 생략함으로써 코드를 줄일 수 있습니다.

출처

프로그래머스 타켓넘버 문제

소스코드

Github 소스코드