[프로그래머스] 타겟 넘버 (Javascript)

문제 설명

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

입출력 예

[1, 1, 1, 1, 1]

3

5

입출력 예 설명

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

 

function solution(numbers, target) {
    var answer = 0;
    recur(0, 0);
    return answer;

    // 재귀함수 형태의 DFS 구현
    function recur(cnt, sum){
        
        // numbers의 모든 수를 연산하고, target과 같은 합이 나오면 answer증가
        if(cnt === numbers.length){
            if(sum === target)
                answer++;
            return
        }

        // + , - 연산 모두 수행
        recur(cnt+1, sum+numbers[cnt]);
        recur(cnt+1, sum-numbers[cnt]);
    }
}

 

문제의 설명이 부족해서 많이 해멨다. 왜냐하면, 입력 예제에서 [1, 1, 1, 1, 1]이 순서대로 지켜져야 하는지 아닌지의 여부가 정확히 명시되어 있지 않았다. 그래서 '순서가 중요하지 않은' 형태로 문제를 접근하여 오랜 시간에 해결했으나 빨간색 실패가 와르르 생겼다. 주식이었으면 빨간색이 반갑겠지만 아쉽다. 따라서, '순서가 중요한' 형태로 구현하였다. 

 

numbers 배열의 원소를 DFS를 통해 합을 구하도록 구현하였다. 아래는 예시이다. 

 

0        1         2

                -> +1

      -> +1

                -> -1

0              

                -> +1

      -> -1

                -> -1  .....  

 

 

이러한 형태로 계속해서 더해지는 깊이 우선 탐색을 재귀함수로 구현하였다.

 

종료 조건으로는 cnt가 numbers의 길이만큼 수행했다는 것은 모든 원소를 연산했다는 것이고, 또한 target과 모두 연산된 sum이 같다면 answer를 증가하는 방식이다. 

 

문제를 풀다가 당황스러운 에러가 있었다. 

 

위 소스코드에서 재귀함수 호출 부분에서 cnt+1을 cnt++로 했을 때 발생한 에러였다. 

 

에러 발생 원인은 cnt++을 사용하면 cnt가 2이면 다음 재귀 함수에는 3을 인자로 사용해야 하는데, ++후연산을 사용하게 되면 cnt가 2로 인자로 사용된 후 3으로 증가되기 때문이다. 따라서, numbers.length는 5인데, cnt가 6까지 연산을 수행하려해서 인덱스 접근에 오류가 발생한 것이다.