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

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

프로그래머스

 

조건

제한시간 : 45분 이내

이번 문제는 로직정리를 위해 세 가지 정도 정리하고 구현하면 좋을 거 같다.
1. dfs 구현을 할줄 아는가? (재귀적)
2. dfs 구현 중에, 매개변수에서 해당 값을 변환시켜 계속 다음 dfs 호출하는 구현을 해본 적이 있는가?
3. dfs 구현부에서 두 개의 dfs 메서드를 호출해 본 dfs를 만들어본 적이 있는가?

아마 일반적으로 알고리즘 문제를 접한 분은 dfs를 다 구현할 줄 알 것이다.
여기서, dfs 구현 방법 중에, dfs 매개변수에서 값을 문자열 변환 또는 int의 값 연산작업을 해서 넘겨주는 구현을 해본 사람들도 있고 안 해본 사람들도 있다.

일단, 문제로 돌아가서 우리는 Input data 로 들어온 target 이라는 값을 +,- 를 이용해서 만들어야 하며, 총 몇 개의 경우의 수가 있는 지 개수 카운트를 해줘야 한다. 고로, input data 로 들어온 number.length 만큼 그래프 depth 까지 들어갔으면, 매개변수로 계속 넘겨 받은 연산된 값(accureValue)을 확인하면 되는 식으로 구현하면 된다.

하지만, 여기서 어떻게 +,- 를 모든 경우의 수를 따져가며 계산해서 target 값을 찾을 수 있을까?
이 부분은, dfs 구현부 안에서 dfs 를 + 한 번, - 한 번해서 총 두 번의 호출을 통해서 모든 경우의 수를 찾아갈 수 있다.

아래 코드를 확인해보자.

class Solution {
    int count = 0;
    public int solution(int[] numbers, int target) {
        // dfs(input값, 그래프depth, input값, 연산작업을 하는 변수)
        dfs(numbers, 0, target, 0); // 1. dfs 호출

        return count;
    }
    
    public void dfs(int[] numbers, int depth, int target, int accrueValue) {
    	// 2. numbers의 수만큼 연산작업을 이행했니?
        if (depth == numbers.length) {
            // 2-1. 연산작업을 다 이행했다면, 이행한 값이 target과 값이 일치하니?
            if (target == accrueValue) count++;
            
            return;
        }
        

        dfs(numbers, depth+1, target, accrueValue + numbers[depth]);   // 3. +연산 dfs 돌리기
        dfs(numbers, depth+1, target, accrueValue - numbers[depth]);   // 3-1. -연산 dfs 돌리기
    }
}