[JS] 타겟 넘버

 

 

난이도: Lv. 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

알고리즘

누적 합을 나타내는 변수는 sum, 위 그림에서 -1과 1을 나타내는 변수는 flag, 트리의 레벨을 나타내는 변수는 idx이다.

1. sum에 flag와 주어진 정수 배열에서 idx에 해당하는 원소를 곱하여 더하고, idx를 하나 증가시킨다. 

2. idx가 주어진 배열의 길이와 같아지면 주어진 배열의 원소들을 연산한 것이기 때문에 재귀함수를 종료한다. 종료하기 전 누적 합인 sum과 타겟 넘버가 일치하는지 확인한다.

3. idx가 주어진 배열의 길이보다 작을 경우 주어진 배열의 모든 원소를 연산하기 위해 위 과정을 반복한다.

 

 

코드

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

    function dfs(sum, flag, idx) {
        sum += flag * numbers[idx++];

        if (idx === numbers.length) {
            if (sum === target) { answer++; }
            return;
        }

        dfs(sum, -1, idx);
        dfs(sum, 1, idx);
    }

    dfs(0, -1, 0);
    dfs(0, 1, 0);

    return answer;
}

 

 

주저리

사실 처음 통과한 코드는 dfs가 아니였다.

function dec2bin(num, length) {
    let result = num.toString(2);
    const endLoop = result.length;
    for (let i = 0; i < length - endLoop; i++) {
        result = "0" + result;
    }

    return result;
}

function solution(numbers, target) {
    var answer = 0;
    const endLoop = Math.pow(2, numbers.length);

    for (let i = 1; i < endLoop; i++) {
        const bin = dec2bin(i, numbers.length);
        let sum = 0;
        for (let j = 0; j < numbers.length; j++) {
            if (bin[j] == 0) { sum += -1 * numbers[j]; }
            else { sum += numbers[j]; }
        }
        if (sum === target) {
            answer++;
        }
    }

    return answer;
}

어떻게 dfs로 풀 것인지 짱돌 굴리다가 굳이 dfs로 풀어야하나 라는 생각이 들었다. 1부터 2^(배열의 길이)까지 2진수로 바꿔서 0인 비트는 빼고 1인 비트는 더하는 식으로 풀었는데 풀리긴한다. 그러나 매우 느리다.

 

남들 dfs로 어떻게 푸나 질문하기를 떠돌아 다니다가 js 정답 코드 봤는데 코드가 너무 짤망해서 현타왔다. 나는 함수 안에 또 함수 선언하는게 매우 어색하고 이래도되나 싶은데 따로 선언해서 풀다가 왜 그렇게 하는지 깨달았다. 따로 선언하면 넘겨줘야할 인자가 많아진다. 그건 둘째치고 코드 슥 읽어보고 직관적이지 않다고 느껴져서 C++ 코드 보니까 어떻게 해야할지 감이와서 다시 풀었는데 노드 레벨 이상하게 계산해서 삽질 좀 했지만 아무튼 풀었고 위 코드보다 훨씬 빠르다.