7. DFS & BFS - 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

• BFS,DFS - 타겟 넘버
  

메인 아이디어

• 숫자는 1 <= n <= 50 / 중복은 안되고 , 연산자는 +,- 중복 가능
• 재귀로 마지막 연산자까지 조합후 결과 값이 3일 경우 카운트한다.
• 카운트된 숫자를 리턴한다.

1. 재귀 할 함수를 만든다.
   void Solution ( int tmp_length ( 깊이라고 생각 할 수 있음 ) )

• 깊이가 numbers.length의 2배 일경우 조합을 계산하여 값이 3일 경우 카운트한다.

2. 조합을 계산할 함수
   void calulation ( String combination )

• 연산자 배열과 피연산자 배열 2개의 배열로 분리한다.
• 2개의 배열에서 앞부터 한개씩 꺼내서 계산한 결과를 int ret에 저장한다.
• 첫 연산자는 기호연산자기에 조건문을 추가한다. 초기값 0에다 연산하게 되면 해결

1차 코드 ( 런타임 에러(스택오버), 시간 초과 )

import java.util.HashSet;

public class Programmers_43165 {
    public static void main(String[] args) {
        int numbers [] = { 1,1,1,1,1 }, target = 5, count = 0;
        Solution s = new Solution(numbers, target);
        for(String i:s.combinations) {
            count++;
        }
        System.out.println(count);
    }
}

class Solution{
    int numbers [], target = 0, ret_count = 0;
    boolean is_used [];
    HashSet<String> combinations = new HashSet<String>();
    Solution( int [] numbers, int target ){
        this.numbers = numbers;
        this.target = target;
        this.is_used = new boolean[numbers.length];
        recursive(0);
    }
    String combination = "";

    void recursive(int depth){
        String prev_combination = combination;
        if( depth == numbers.length && calculate(combination) == target ){
            if ( calculate(combination) == target ){
                combinations.add(combination);
            }
            return;
        }
        for(int i=0;i< numbers.length;i++){
            if(is_used[i]){ continue; }
            is_used[i] = true;
            combination = prev_combination + "+"+numbers[i];
            recursive(depth + 1);
            combination = prev_combination + "-"+numbers[i];
            recursive(depth + 1);
            combination = prev_combination;
            is_used[i] = false;
        }
    }

    int calculate(String combination){
        //연산자배열, 피연산자배열로 나누기
        int length = combination.length() / 2;
        char [] op = new char[length];
        int [] num =  new int[length];
        int op_idx = 0, num_idx = 0;
        for(int i=0;i<combination.length();i++){
            if(i%2==0) {
                op[op_idx++] = combination.charAt(i);
            } else {
                num[num_idx++] = combination.charAt(i)-'0';
            }
        }
        //두 배열 제일 앞요소부터 꺼내서 조합
        int ret = 0;
        op_idx = 0;
        num_idx = 0;
        for(int i=0;i<op.length;i++){
            if(op[i] == '+'){ ret += num[i]; }
            else if(op[i] == '-') { ret -= num[i]; }
        }
        return ret;
    }
}

1차 이후 다시 본 조건

• 주어진 numbers 배열 그대로만 사용하는 것인가?
• 그대로만 사용해야 하는 것이면 중복된 조합이 나올 수가 없기 때문에 계산하는 메서드는 필요없다.

너무 열받고 어이없는 2차 코드(통과)

public class Programmers_43165_recursive {
    static int count = 0;
    static int [] numbers;
    static int target = 0;
    public static void main(String[] args) {
        numbers = new int []{1, 1, 1, 1, 1};
        target = 3;
        recursive(0,0);
        System.out.println(count);
    }
    static void recursive(int depth, int sum){
        if(depth == numbers.length){
            if( sum == target)count++;
            return;
        }
        recursive(depth+1,sum + numbers[depth]);
        recursive(depth+1,sum - numbers[depth]);
    }
}