Algorithm/깊이 우선 탐색

[프로그래머스/43165번/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 이하인 자연수입니다.

입출력 예

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

풀이에 사용할 알고리즘 구상

완벽하게 DFS 사용을 권장하고 있는 문제다. 문제 제한사항이 빡빡하지 않기 때문에 DFS를 써서 주어진 numbers에 담긴 숫자를 전부 더하거나 빼거나 해 볼 수 있다.

 

첫 숫자부터 다음 숫자로 넘어갈 때마다 더하거나 빼거나 두 가지 경우로 나누어지고 이 '나눠짐'이 최대 20번 이하로 발생하기 때문에 최대 연산 횟수는 220으로 고작 100만 번 가량이라 이 방법을 사용해도 시간 초과가 발생하지 않는다. 코딩 테스트에선 보통 연산이 10억 번 미만으로 발생하면 안정적으로 통과할 수 있다고 생각해도 된다. 물론 대략적인 수치고, 각 연산마다 서로 다른 복잡도 등을 고려하면 수치가 달라질 수 있으므로 대략적으로 10억 번이 한계라고 가늠만 하면서 문제를 풀자.

 

DFS에 대한 기본 설명은 생략한다. 나는 DFS 함수의 매개변수로 깊이와 지금까지 거쳐온 수의 합을 전달했고, 그 깊이가 numbers에 담긴 숫자의 최대치만큼 깊어졌을 때 DFS 함수를 반환하도록 했다. 반환할 때, 지금까지 거쳐온 수의 합이 target과 일치하다면 정답을 1 늘리면 된다. 다음 깊이로 내려갈 때, 숫자를 더하거나 뺄 수 있으므로 더하면서 내려가거나 빼면서 내려가거나 두 가지 상황으로 분기하면 된다. 다만 이렇게 한다면 똑같은 경우를 두 번 계산하게 되므로 최종 답안은 2로 나눠야 한다.

제출 코드

function solution(numbers, target) {
    let answer = 0;

    const dfs = (index, curVal, sign) => {
        if (index === numbers.length) {
            if (curVal === target) answer++;
            return ;
        }

        if (sign) {
            dfs(index+1, curVal+numbers[index], true);
            dfs(index+1, curVal+numbers[index], false);
        } else {
            dfs(index+1, curVal-numbers[index], true);
            dfs(index+1, curVal-numbers[index], false);
        }

    }

    dfs(0, 0, true);
    dfs(0, 0, false);

    return answer/2;
}
raejoonee