[프로그래머스] 타겟 넘버 - 자바스크립트(JavaScript)

프로그래머스의 깊이/너비 우선 탐색(DFS/BFS) 관련 문제들 중 하나인 타겟 넘버를 풀어보았다. 이 문제는 DFS(Depth First Search) 문제일 것이다.

문제 파악

 다음과 같이 사용할 수 있는 숫자가 담긴 배열과 타겟 넘버가 매개변수로 주어지며, 이 숫자들을 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 구해야하는 문제이다. 

 

-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

 

 최단 거리를 구하는 문제가 아닌, 모든 경우의 수를 따져보아야하는 문제였다. 위의 예시에서는 배열의 길이가 5이므로 총 경우의 수는 32가지이다. 즉 주어진 배열의 길이가 N개라면 2 ** N(2의 N승)의 경우의 수가 존재하는 것이다.

 

 경우의 수는 알았지만 어떻게 구현할지 고민하다가 2진법이 떠올랐다. 주어진 배열의 각 숫자가 + 혹은 - 의 부호를 가지므로 0과 1로 표현할 수 있기 때문이다. 그렇게 이 방법으로 구현을 해보기로 하였다.

 

풀이 과정

1. 주어진 길이 N 까지의 모든 2진수 구하기

 자바스크립트로 10진수를 2진수로 변환하는 방법은 다음과 같다.

var dec = 6;
var bin = dec.toString(2); 
// return "110"

 

 하지만 "0001"과 같이 앞의 자리에도 "0"을 추가하는 작업이 필요했다. 다음 예시처럼 padStart를 이용하여 앞자리의 "0"을 추가해주었다.

let number = 6;

let result = number.toString(2).padStart(5, '0');

//result : 00110

 

 그리고 이렇게 주어진 2진수 문자열을 순환하여야 하므로 split을 사용하여 배열로 만들었다.

let bin = "00110";

let result = bin.split("")

//result : [ '0', '0', '1', '1', '0' ]

2. 각 케이스별 부호를 대입하여 target 과 같은지 판별

 0부터 시작하여 2 ** N 까지 순환하는 반복문에서 각각의 2진수를 구한다.

 

 그리고 해당 2진수 부호 조합에 따라 numbers 배열의 숫자들을 forEach를 이용하여 계산했다.

 

 계산 결과 값이 target 값과 같을 경우 answer 값을 1씩 증가시켜주고, 모든 과정이 끝났을 경우 답을 도출 할 수 있다.

 

최종 풀이

function solution(numbers, target) {
    var answer = 0;
    var length = numbers.length
    for(var i = 0; i < 2 ** length; i++) {
        var tmp = i.toString(2).padStart(length, "0").split("");
        var result = 0;
        numbers.forEach((value, index) => {
            if(tmp[index] === "0") {
                var d = 1
            } else if (tmp[index] === "1") {
                var d = -1
            }
            result = result + value * d;
        })
        
        if(result === target){
            answer++;
            console.log(result, target)
        }
    }
    return answer;
}

 

후기

 문제 풀이 통과는 하였지만, 깊이/너비 우선 탐색과 관련된 문제를 편법으로 해결했던 것 같았다.

 

 문제 풀이를 완료한 뒤 다른 사람의 풀이를 보았는데 정말 좋은 풀이들이 많았다. 그 중 가장 멋지다고 생각되는 풀이를 소개하고 싶다.

 

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0,0);
    function getAnswer(x,value) {
        if(x<numbers.length){
            getAnswer(x+1,value + numbers[x]);
            getAnswer(x+1,value - numbers[x]);
        } else{
            if(value === target){
                answer++
            }
        }
    }
    return answer;
}

 

 이 코드를 보면 말 그대로 나뭇가지가 쭉 뻗어나가는 그림이 상상된다. 이 풀이를 통해 DFS에 대해 조금 더 깊은 이해를 할 수 있었다.