[프로그래머스 코딩테스트 연습] 타겟 넘버 - javascript

개요

난이도 level 2

문제

문제 설명

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 이하인 자연수입니다.

입출력 예numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

풀이

function solution(numbers, target) {
    let answer = 0
    
    dfs(0,0)
    
    function dfs(sum, index){
        if(index===numbers.length){
            if(target===sum){
                answer++
            }
            return
        }
        dfs(sum+numbers[index], index+1)
        dfs(sum-numbers[index], index+1)
    }
    
   return answer 
}

느낀점

이번문제는 플러스와 마이너스를 할 경우를 중복수열로 미리 구해놓고

해당 경우의수를 모두 순회하며 값을 구하려고했었다

 

그런데 히든케이스 1번과 2번에서 런타임에러 발생..

아마 배열의 길이가 너무길어서 스택플로우 난것같다..(아마도?)

 

그래서 그냥 질문 둘러보다가 dfs나 bfs로 푸는거라기에

냅다 dfs로 시도

 

코드도 짧고 빨리 풀렸다