프로그래머스 - 타겟 넘버 - DFS(재귀, Stack) - Java

1. 문제

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

✨DFS, 재귀 차이(?)

DFS는 재귀로 구현됩니다. 재귀는 콜 스택이 쌓이는 형식이기 때문에 직접 Stack으로도 구현할 수 있습니다.

---

현재 문제에서는 탐색 공간에서 서로 다른 경로를 선택합니다. 또한, 서로 다른 방식으로 도달한 상태에서 서로 다른 연산자를 쓰기 때문에 중복이 발생하지 않습니다. 따라서 중복 검사가 필요 없습니다.

2-1. 재귀 풀이

재귀적으로 부호를 붙여가며 판단한다.

3-1. 재귀 코드

import java.util.*;

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        //answer = Integer.parseInt("-" + "2");
        dfs(0, 0, numbers, target);
        return answer;
    }
    
    public void dfs(int depth, int sum, int[] numbers, int target){
        if(depth == numbers.length){
            if(sum == target) answer++;
            return;
        }
        
        /*
        String numS = String.valueOf(numbers[depth]);
        int minus = Integer.parseInt("-" + numS);
        int plus = Integer.parseInt("+" + numS);
        
        dfs(depth+1, sum + minus, numbers, target);
        dfs(depth+1, sum + plus, numbers, target);
        */
        dfs(depth+1, sum + numbers[depth], numbers, target);
        dfs(depth+1, sum - numbers[depth], numbers, target);
    }
}

2-2. Stack 풀이

재귀를 잘 Stack으로 구현한 것입니다. 개인적으로는 재귀가 이해하기 훨씬 수월한 것 같다.

3-2. Stack 코드

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        Stack<State> stack = new Stack<>();
        
        stack.push(new State(0, 0));
        
        while(!stack.isEmpty()){
            State state = stack.pop();
            
            if(state.index == numbers.length){
                if(state.sum == target){
                    answer++;
                }
                continue;
            }
            
            stack.push(new State(state.index+1, state.sum + numbers[state.index]));
            stack.push(new State(state.index+1, state.sum - numbers[state.index]));
        }
        return answer;
    }
}

class State {
    int index;
    int sum;
    
    public State(int index, int sum){
        this.index = index;
        this.sum = sum;
    }
}