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

프로그래머스

모든 경우의 수를 탐색해야하는 문제이다보니 재귀함수를 선언하여 DFS로 해결했다.

 

- int[] numbers를 탐색하며 마지막 인덱스까지 각 idx의 숫자를 더하거나 뺌

- idx가 마지막인 경우, sum을 target과 비교하여 일치하면 경우의 수 1을, 일치하지 않으면 0을 반환함

- 반환할 때마다 경우의 수가 더해져 최초 호출된 메서드는 전체 경우의 수를 반환함

 

Note

- 멤버 변수(lastIdx, targetNum, targetNums)는 메서드를 간단하게 작성하고 싶어 사용했다.

- 간단한 문제인데 밤에 풀어서 그런가 종료조건이 명확하게 코드로 바로 나오지 않아 생각하는데 시간이 좀 걸렸다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        lastIdx = numbers.length - 1;
        targetNum = target;
        targetNums = numbers;
        
        answer = calculate(-1, 0);
        
        return answer;
    }
    
    private int lastIdx, targetNum;
    private int[] targetNums;
    
    private int calculate(int idx, int sum){

        if(idx == lastIdx){
            return sum  == targetNum ? 1 : 0;
        }
        
        return calculate(idx + 1, sum + targetNums[idx + 1]) + calculate(idx + 1, sum - targetNums[idx + 1]);
    }
}