programmers 깊이/너비 우선 탐색(DFS/BFS) 타겟 넘버

문제

---

문제 설명

 

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

내 풀이

---

function solution(numbers, target) {
    
    var compare = [];
    var answer = 0;
	    
	compare.push(addDfs(0, numbers, 0, compare));
	compare.push(subDfs(0, numbers, 0, compare));
	
    for(var i in compare){
        if(target == compare[i]){
            answer++;
        }
    }
    
	return answer;
}

function addDfs(i, numbers, sum, compare){
		
	    sum += numbers[i];
	   
	    if(numbers.length == i+1){
	    	compare.push(sum);
	        return compare;
	    }
	    
	    
	    addDfs(i+1, numbers ,sum, compare);
	    subDfs(i+1, numbers ,sum, compare);
	    
	    return;
	}
	
	function subDfs(i, numbers, sum, compare){
		
	    sum -= numbers[i];
	    
	    if(numbers.length == i+1){
	    	compare.push(sum);
	        return compare;
	    }
	    

	    addDfs(i+1, numbers ,sum, compare);
	    subDfs(i+1, numbers ,sum, compare);
	    
	    return;
	}

처음에 문제를 보고 어떻게 풀까 고민을 좀 해봤다.

 

최근 독학사 2단계 준비한다고 자료 구조를 공부해서 그런가

 

깊이/너비 우선 탐색을 보고 트리 형식으로 접근하면 되겠다고

 

생각을 해서 대략적으로 이진 트리를 머릿속에 그려봤다.

 

중요 포인트는 받는 정수의 앞에 부호를 결정해 주면 된다는 것이었고,

 

이에 경우의 수는 32개가 생길 것이고 이를 배열에 담아

 

비교를 해서 answer을 카운트해준다는 식으로 접근했다.

 

하지만 이를 어떻게 구현할 것인가를 고민하다 재귀 호출을

 

쓰면 되지 않을까 싶어 이것저것 시도해보다가 결국 테스트를

 

통과하긴 했는데 연습할 때 콘솔 창에 undefined가 한 개씩 추가되는 것은

 

왜 그런지 아직도 모르겠다. 또한 다 풀고 나서 다른 사람의 풀이를 보니

 

한 개의 함수로 sum 부분에 연산 처리해서 인수를 넘기는 방법이 있었다.

 

테스트 통과하고 다른 사람 풀이 보면서 항상 느끼는데 

 

코드가 이렇게 아름다울 수 있구나 하면서 좋은 깨달음을 얻는다.