자바(JAVA) - 타겟 넘버(Programmers : 43165)

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

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

DFS 알고리즘을 사용하여 입력값의 덧,뺄셈에 대한 모든 결과값을 확인할 수 있었음.
재귀 함수를 구현하였으며, 각 연산에 대한 재귀호출 + 예외처리 + 정답에 대한 조건문만으로 쉽게 풀 수 있었던 문제.

 

실행 순서는 다음과 같다 :

    1. 초기값을 넘겨 dfs 재귀함수 호출

    2. 다음 index 값 & result값을 넘기며 덧셈 & 뺄셈에 대한 재귀 호출

    3. 배열의 마지막 값까지 확인했을 경우, result값이 target값과 동일할 경우 answer 값 증가

    4. answer 반환

 

 

<코드>

import java.util.*;

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        
        // dfs 함수 호출 
        dfs(numbers, 0, 0, target);
        
        return answer;
    }
    
    // 나올 수 있는 모든 값들을 구하기 위한 재귀 함수   
    public void dfs(int[] numbers, int index, int ret, int target) {
        // 모든 배열 값들에 대한 연산을 마쳤을 경우
        if(numbers.length == index){
            // 타겟 넘버가 1 미만일 경우에 대한 예외처리
            if(ret < 1) 
                return;                        
            // target값과 동일할 경우 count 증가
            if(ret == target)
                answer++;
            
            return ;
        }

        // 덧셈 & 뺄셈 에 대한 재귀호출
        dfs(numbers, index + 1, ret + numbers[index], target);
        dfs(numbers, index + 1, ret - numbers[index], target);
    }
}