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

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

 

 

** Javascript

 

function solution(numbers, target) {
    let answer = 0;
    function dfs(nodeList, index) {
        if (index < nodeList.length) {
            nodeList[index] *= 1;
            dfs(nodeList, index + 1);
            nodeList[index] *= -1;
            dfs(nodeList, index + 1);
        } else {
            let sum = nodeList.reduce((acc, node) => acc + node, 0);
            if (sum === target) answer++;
        }
    }
    dfs(numbers, 0);
    return answer;
}

 

 

 

 

** Python

 

 

 

 

 

마우스 패드에 직접 그려서 이상하지만

 

일단 임의의 한 값에 +/- 가 반복되어 나눠 들어가는 dfs 구조로

 

메소드 안에 -값 재귀와 +값 재귀를 포함해야 한다는 것까지는 파악했다.

 

그리고 answer에 더해서 값을 누적하는 것보다 target 에서 값을 빼는 방법이 재귀적으로 가능할 것 같았다.

 

여기까지는 생각으로는 가능했는데

 

코드로 결국 풀어내기는 어려웠다

 

 

 

 

 

추천 1등 풀이

 

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

 

아래 코드가 내 거

1등 풀이를 참고했음^^7

사실 거의 똑같다 ㅋㅋㅋㅋㅋ 하지만 나는 조건문에 not 사용하는 것을 지양하므로

 

 

 

 

def solution(numbers, target):
    if numbers:
        return solution(numbers[1:], target + numbers[0] * -1) + solution(numbers[1:], target + numbers[0])
    if not numbers and target == 0: return 1
    else : return 0