프로그래머스 타겟넘버

문제 바로가기

🙄 문제 이해

+, - 연산자를 이용해 타겟 넘버를 찾는 문제입니다.
시작을 0으로 두고 numbers 배열의 앞에서 부터 순서대로 숫자에 +/-를 적용한 경우의 수를 전부 찾아서 결과를 확인하면 될 것 같다고 생각했습니다.

📝 문제 풀이

이진트리를 이용한 DFS를 사용했습니다.
모든 경우의 수에 대해 결과를 찾고, 그 결과가 Target Number와 같은지 확인합니다.

idx를 늘려가며 가장 앞의 수 부터 체크하며, 재귀를 통해 다음 idx로 넘어갈 때 total(합)과 idx를 다음 순서에 맞게 갱신합니다.

마지막 idx에 다다르면 타겟넘버와 같은지 다른지 확인 후 같다면 answer에 +1 해줍니다.

💻 Python 코드

#프로그래머스 타겟넘버

def dfs(numbers, target, total, idx):
    global answer
    if idx == len(numbers):
        if total == target:
            answer += 1
        return
    
    dfs(numbers, target, total + numbers[idx], idx + 1)
    dfs(numbers, target, total - numbers[idx], idx + 1)
        
answer = 0

def solution(numbers, target):
    global answer
    idx = 0
    total = 0
    
    result = dfs(numbers, target, total, idx)
    
    return answer

💻 JavaScript 코드

let answer = 0;

const dfs = (numbers, target, total, idx)=>{
    if (idx == numbers.length) {
        if (total == target) answer += 1;
        return;
    }
    dfs(numbers, target, total + numbers[idx], idx + 1);
    dfs(numbers, target, total - numbers[idx], idx + 1);
}

function solution(numbers, target) {
    let total = 0;
    let idx = 0;
    
    dfs(numbers, target, total, idx);
    return answer;
}

💻 Java 코드

class Solution {
    int answer = 0;
    public void dfs(int[] numbers, int target, int total, int idx) {
        if (idx == numbers.length) {
            if (total == target) answer += 1;
            return;
        }
        
        dfs(numbers, target, total + numbers[idx], idx + 1);
        dfs(numbers, target, total - numbers[idx], idx + 1);
    }
    
    public int solution(int[] numbers, int target) {
        int total = 0;
        int idx = 0;
        
        dfs(numbers, target, total, idx);
        return answer;
    }
}