[프로그래머스] 타겟 넘버(java)

코딩테스트 연습 - 타겟 넘버 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

서로 다른 수들의 합 또는 차로 타겟 넘버가 결정되기 때문에 모든 경우를 직접 계산하여 확인하여야 한다고 생각했다.

k번째 정수까지 계산을 끝냈을때 k+1번째 정수는 + 또는 -로 두가지 경우의 결과를 계산하여야 합니다.

이러한 문제를 DFS(깊이 우선 탐색)을 통해 간단한 코드로 해결하고자 하였습니다.

 

코드

 class Solution {
    public int solution(int[] numbers, int target) {
        int answer = dfs(numbers,0,0,target);
        
        return answer;
    }
    public int dfs(int[] numbers, int depth, int sum, int target){
        if(depth==numbers.length){
            if(target == sum) return 1;  
            else return 0;
        } 
        else{
            return dfs(numbers,depth+1,sum+numbers[depth],target) 
                + dfs(numbers,depth+1,sum-numbers[depth],target);
        } 
    }
}

n번째 정수까지 계산한 후 결과 값이 타겟넘버와 같다면 1, 아니라면 0을 리턴하는 DFS함수를 작성하였습니다.

작성한 DFS를 호출하고 리턴함으로서 원하는 결과를 얻을 수 있습니다.