프로그래머스 Lv2 타겟 넘버

문제

링크

설명

answer = 0

def dfs(i, numbers, target, value) :
    global answer
    # numbers 안의 모든 수를 다 계산했는데 target 값과 같을 때
    if i == len(numbers) and target == value :
        answer += 1
        return
    
    # target 값이 나오지 않았지만 numbers 안의 모든 수를 다 계산했을 때
    if i == len(numbers) :
        return
    
    # 더하거나 빼기
    dfs(i+1, numbers, target, value + numbers[i])
    dfs(i+1, numbers, target, value - numbers[i])
    
def solution(numbers, target) :
    global answer
    dfs(0, numbers, target, 0)
    return answer

     0 
   /   \
 -1     1
 / \   /  \
-1  1 -1  1
    ...

이렇게 진행되기 때문에 dfs로 풀 수 있다.

dfs/bfs 트리 관련 문제도 많이 풀어야겠다..

• 2022-08-03

function solution(numbers, target) {
    const answer = [];
    let i = 0;
    bfs(numbers, target, answer, 0, 0);
    return answer.length;
}

function bfs(numbers, target, answer, save, i) {
    if (i === numbers.length) {
        if (save === target) {
            answer.push(save);
        }
        return ;
    }
    bfs(numbers, target, answer, save-numbers[i], i+1);
    bfs(numbers, target, answer, save+numbers[i], i+1);
}

function solution(numbers, target) {
    let answer = 0;
    let i = 0;
    
    function bfs(numbers, target, save, i) {
        if (i === numbers.length) {
            if (save === target) {
                answer++;
                console.log(answer)
            }
            return ;
        }
        bfs(numbers, target, save-numbers[i], i+1);
        bfs(numbers, target, save+numbers[i], i+1);
    }
    bfs(numbers, target, 0, 0)
    return answer;
}

자바스크립트를 이용해서 풀었다.
함수 내부에 또 함수를 선언하여 변수 하나에 넣어 문제를 푸는 것보다 따로 함수를 빼고 답이 나올 때마다 배열에 값을 넣어 길이를 구할 때가 더 답이 빠르게 나왔다. 흠