[프로그래머스,자바] Level2 : 타겟 넘버

문제분석

여러개의 숫자가있는 배열 numbers와 target이 입력으로 주어집니다.

 

목표: numbers의 숫자를 모두활용하여, + - 만으로 target을 만드는 경우의수를 세기 

 

모든 숫자를 사칙연산중 +,-만을 활용하여 target이 나오는경우를 세주면된다.

사칙연산중 2개의 연산만 고려하면되니, 재귀함수를 활용하면 간단하게 풀수있다.

문제풀이

class Solution {
    boolean[] visited;
    int cnt=0;
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        visited=new boolean[numbers.length];
        recursive(numbers,0,target);
        return answer=cnt;
    }
    
    public void recursive(int[] numbers,int idx,int target){
        //재귀 로직
        for(int i=idx;i<numbers.length;i++){
            visited[i]=true;
            recursive(numbers,i+1,target);
            visited[i]=false;
        }
        
        //연산 시작
        int total=0;
        for(int i=0;i<numbers.length;i++){
            if(visited[i]==true){
                total+=numbers[i];
            }
            else{
                total+=numbers[i]*(-1);
            }
        }
        //타겟과 맞는지확인
        if(total==target){
            cnt++;
        }
    }
}