[알고리즘] 프로그래머스 - 타겟넘버 LV02 Java

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

프로그래머스

package Programmers;

import java.util.Arrays;

public class 타겟넘버 {

    static int[] combArr = {1, -1};
    static int[] chMap;
    static int tempAnswer;
    public static void main(String[] args){
        타겟넘버 T = new 타겟넘버();
        int[] numbers = {1, 1, 1, 1, 1};
        int target = 3;
        T.solution(numbers, target);
    }

    public int solution(int[] numbers, int target) {
        chMap = new int[numbers.length];
        tempAnswer = 0;
        dfs(0, numbers, target, new int[numbers.length]);
        return tempAnswer;
    }
    public void dfs(int L, int[] numbers, int target, int[] myArr){
        if(L == numbers.length){
            int sum = Arrays.stream(myArr).sum();
            if(sum == target) tempAnswer++;
            return;
        }else{
            for (int i = 0; i < combArr.length; i++) {
                myArr[L] = combArr[i] * numbers[L];
                dfs(L + 1, numbers, target, myArr);
            }
        }
    }
}

 

1. 풀이 

   1.1 ) combArr 에  [-1, 1] 들어있는 배열을 만든다.

   1.2 ) dfs 를 돌면서 myArr을 만든다. 

           -> 기존 numbers 조합배열에 combArr 을 곱한조합의 배열 

                넣게되면 배열은 -1, 1 을 곱한 numbers 의 모든 조합의 수를 구할수가있음 

   1.3 ) L 은 DFS의 레벨값이다. 레벨값이 numbers 배열의 길이와 같다면 구해진 myArr조합의 합을 구해 target과 같은지 비교하고 

           같다면 answer에 +1 을 해준다.