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

🔗 문제 링크

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

👨🏻‍💻 내가 작성한 코드

import java.util.*;

class Solution {
    static int count = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, 0, target);
        
        return count;
    }
    
    public static void dfs(int[] numbers, int currentRow, int sum, int target) {
        if (currentRow == numbers.length){
            if(sum == target)
                count++;
        }
        else {
            for (int i = 0; i < 2; i++){
                if(i==0) {
                    sum += numbers[currentRow];
                    dfs(numbers, currentRow+1, sum, target);
                    sum -= numbers[currentRow];
                } 
                else {
                    sum -= numbers[currentRow];
                    dfs(numbers, currentRow+1, sum, target);
                    sum += numbers[currentRow];
                }
            }
        }
    }
}

👨🏻‍💻 다른 사람의 풀이

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

📝 결론

처음으로 DFS를 활용한 알고리즘 문제를 풀어봤다.
문제를 보고 DFS를 통해 해결해야하는 것을 인지하고 DFS함수를 만들어 문제 해결을 하였으나 처음이라 그런지 문제에 적용을 하는데 오랜 시간이 걸렸으며 결과인 count를 return할 방법을 생각하지 못하여 global variable로 static변수를 만들어 사용한 한계가 있었다.

문제를 풀고 다른 사람의 풀이를 보니 같은 logic임에도 불구하고 코드가 간결하고 내가 하지 못한 결과도 쉽게 return하였다.

앞으로 나도 DFS 코드를 짤 때 저 분의 코드와 같이 간결하고 쉽게 짜도록 노력해야겠다.