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

문제

 

풀이코드

static int answer = 0;                          	//답을 static변수로 설정
public int solution(int[] numbers, int target) {
    DFS(0,0,numbers,target);
    return answer;
}

public void DFS(int L, int sum, int[] arr, int target){     //타겟 넘버를 계산해줄 메서드 생성
    if(L == arr.length){                                    //L(레벨)이 arr의 길이와 같을 경우
        if(sum == target){                                  //합(sum)과 target의 값이 같으면 answer을 1증가
            answer++;
        }
    }else{                                              //L(레벨)이 arr의 길이와 다를 경우
        DFS(L+1,sum+arr[L],arr,target);        		//합에 arr[]값을 더한 것을 재귀
        DFS(L+1,sum-arr[L],arr,target);        		//합에 arr[]값을 뺀 것을 재귀
    }
}

이 문제는 DFS와 재귀함수의 원리를 이용하면 풀기 쉬운 문제인 것 같다.

근데 다른 분의 풀이를 보니 원리는 똑같은데 뭔가 좀 더 빠른 것 같아서 가져와봤다.

 

다른사람의 풀이

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

내 풀이가 이해가 갔다면 이 풀이도 쉽게 이해할 수 있을 것이라 생각하여 따로 설명은 안붙이겠다.

내 풀이는 주석에 써놓았다.