프로그래머스 - DFS - 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버

import java.util.Stack;

public class 타겟_넘버 {
    public static void main(String[] args) {
        타겟_넘버 o = new 타겟_넘버();
        System.out.println(o.solution(new int[]{1,1,1,1,1}, 3));
    }

    private static int[] numbers;
    private static int target;
    private static int count = 0;
    public int solution(int[] numbers, int target) {
        타겟_넘버.numbers = numbers;
        타겟_넘버.target = target;
        //permutation(numbers.length, "");
        dfs(0, numbers[0]);
        dfs(0, -numbers[0]);
        return count;
    }

	//순열로 구현
    private void permutation(int depth, String sResult) {
        //종료
        if(depth == 0) {
            int result = 0;
            for(int i=0; i<numbers.length; i++) {
                if(sResult.charAt(i) == '+') {
                    result += numbers[i];
                } else {
                    result -= numbers[i];
                }
            }

            if(result == target) {
                count++;
            }

            return;
        }

        //프로세스
        for(int i=0; i<2; i++) {
            String operator = "";
            if(i == 0) {
                operator = "+";
            } else {
                operator = "-";
            }

            permutation(depth-1, sResult+operator);
        }
    }

	//dfs로 구현
    private void dfs(int index, int result) {
        //종료
        if(index == numbers.length-1) {
            if(result == target) {
                count++;
            }

            return;
        }

        //프로세스
        dfs(index+1, result + numbers[index+1]);
        dfs(index+1, result - numbers[index+1]);
    }
}

알고리즘

• 완전탐색, 순열, DFS
• 순열과 DFS로 각각 구현했는데 DFS로 구현할 경우 좀 더 코드를 깔끔하게 만들 수 있었다.