[Programmers/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 함수를 작성해주세요.

 

 

입출력

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

입출력 #1

문제에 나온 예와 같습니다.

 

 

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

코드

function solution(numbers, target) {
    var answer = 0;
    var sum = 0;
    
    for(var i=0; i<numbers.length; i++) {
        sum+=numbers[i];
    }
    
    const toMake = (sum-target)/2;
    var queue = [{ sum:0, index:0 }];
    
    while(queue.length != 0) {
        var num = queue.pop();
        for(var i = num.index; i<numbers.length; i++) {
            if(num.sum+numbers[i]<toMake) 
                queue.push({ sum:num.sum+numbers[i], index:i+1});
            else {
                if(num.sum+numbers[i] == toMake) answer++;
                continue;
            }
        }
    }
    return answer;
}

 

설명

변수 이름이 queue인 이유는 처음에 shift() 메서드를 사용해서 큐를 구현하여 BFS로 풀었기 때문이다.

그런데 제출해보니 테스트케이스 1번과 2번에서 시간초과가 났다.

그래서 shift()를 pop()로 바꿔서 DFS로 풀었더니 해결됐다.