[프로그래머스 JavaScript] 타켓 넘버

🚩 프로그래머스 Level2 타켓 넘버 -> 깊이/너비 우선탐색(DFS/BFS)

 

📖 문제 설명

주어진 numbers에서 덧셈, 뺄셈을 해서 전부 가능한 경우의 수를 구하면 된다.

그렇게 구한 경우의 수를 target과 비교해서 맞으면 1, 아니면 0을 리턴하면 된다.

 

👉 소스 코드  ⏰시간복잡도 O(2^n)

function solution(numbers, target) {
    var answer = 0;
    
    //numbers, target, 양수(음수)값, 인덱스를 넘겨줌
    answer = targetNumber(numbers, target, numbers[0], 1) + targetNumber(numbers, target, numbers[0] * -1, 1);
  
    return answer;
}

function targetNumber(numbers, target, sum, i){
    //numbers까지 구했으면 target 값과 비교
    if(i === numbers.length){
        if(sum === target) return 1;
        else return 0;
    }
    
    //받은 누적값 sum에 대해 경우의 수(양수, 음수)를 계산하여 재귀호출
    return targetNumber(numbers,target,sum+numbers[i],i+1) + targetNumber(numbers,target,sum+numbers[i]*-1,i+1);
}

 

👨‍💻 코드 설명

코드 로직은 피보나치 수열-재귀 알고리즘을 이용했습니다.

주어진 모든 경우의 수를 구하기 위해 재귀 함수를 이용합니다.

배열 첫번째 값을 양수, 음수의 경우로 나누어 재귀 함수에 넣어줍니다.

재귀 로직을 통해 피보나치 수열과 동일한 로직으로 모든 경우의 수가 구해집니다.

배열의 길이까지 탐색했으면 target 값과 비교하여 리턴해줍니다.