[코딩테스트 javascript] 타겟넘버 - 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 함수를 작성해주세요.

 

 

풀이

1. 문제해석

numbers 배열의 원소가 + 또는 -를 하여 다 더한 숫자가 target인 경우의 수를 출력한다.

 

2. DFS 함수

재귀함수 , 즉 DFS(깊이탐색알고리즘)을 이용해서 문제를 풀어야한다.

DFS 함수 설계시 수행 동작과 탈출 조건을 생각해서 작성한다.

 

function DFS(index,sum) {
        //2. 탈출조건
        if (index===numbers.length){
            if (sum ===target) answer++;
            return 0;
        }
        //1. 수행 동작
        DFS(index+1,sum + numbers[index]);
        DFS(index+1,sum - numbers[index]);
    }

 

DFS(0,0) 입력시 수행되는 코드는 아래와 같다.

손수 작성한 플로우차트이다..!!

 

 

DFS(5,sum)일때, index가 arr.length이기때문에 answer 값을 확인하고 target과 값이 같은지 확인한다.

 

최종 코드는 아래와 같다.

 

function solution(numbers,target) {
    let answer = 0
    function DFS(index,sum) {
        //2. 탈출조건
        if (index===numbers.length){
            if (sum ===target) answer++;
            return 0;
        }
        //1. 수행 동작
        DFS(index+1,sum + numbers[index]);
        DFS(index+1,sum - numbers[index]);
    }
    DFS(0,0);
    return answer;
}