[프로그래머스 | Javascript] 코딩테스트 Lv2 - 타겟 넘버

문제 설명

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

나의 풀이

function solution(numbers, target) {
    let answer=0;
    let array = Array(numbers.length).fill(0);      // 값을 넣어줄 빈 배열 생성
    function def(n){ 
        if(n===numbers.length){     // 배열의 끝까지 돌았다면 중단
            let hap = array.reduce((a,b)=>a+b);     // 배열의 합을 구한다.
            if(hap===target){           // 합이 target과 같으면 answer++
                answer++;
            }
        }else{                          
            array[n]=numbers[n];            // 값을 그대로 대입
            def(n+1);
            array[n]=(-numbers[n]);         // - 부호를 넣어서 대입
            def(n+1);
        }
    }
    def(0);
    return answer;
}

---

이 문제는 DFS/BFS를 사용하여 푸는 문제다. 

이 알고리즘을 사용하여 풀어본 것이 처음이라 처음에는 어색하고 어떻게 풀어야 할지 감을 찾지 못했다. 

그래서 하루 동안 DFS/BFS를 찾아보고 강의도 들은 결과 문제를 풀 수 있게 되었다.

나는 DFS를 이용해서 풀었기 때문에 재귀함수를 사용했다.

다른 사람의 풀이를 보니 재귀함수의 매계변수를 2개를 둬서 풀은 것을 보고 나는 다르게 풀고 싶어서 이렇게 풀어봤다.