94. 타겟 넘버

 

using System;

public class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        return answer;
    }
}

 

이 문제도 DFS 으로 재귀함수를 만들어 깊이 우선 탐색을 진행해야 했다...

(이제는 진짜 이런 문제 밖에 없는 듯...ㅜㅜ)

 

재귀함수는 매개변수가 중요하기 때문에 매개변수로 뭘 줄지 생각해봤다.

 

1. 숫자 배열 numbers

2. 타겟 넘버 target

3. 숫자 배열에서 현재 탐색할 index

4. 현재 계산 결과

 

이렇게 필요하다고 판단 했다. 또한, 재귀함수는 반환형을 어떻게 주느냐에 따라

 

결과가 달라질 수 있는데 반환형을 void로 해도 괜찮을 것 같았다.

 

대신 전역변수로 count를 줘서 타겟 숫자를 찾으면 1씩 증가시켜 줄 생각이다.

(

 

C#은 Class로 이미 캡슐화 돼 있기 때문에 count 변수를 Class의 field 변수로 봐야 한다.

하지만, 현재는 편의상 전역변수라고 지칭하겠다.

 

)

 

using System;

public class Solution {

    //결과를 개수 변수
    public int count = 0;
    
    //필요한 매개변수
    //숫자 배열
    //타겟 넘버
    //현재 index
    //현재 숫자 결과
    public void DFS(int[] numbers, int target, int currentIndex, int currentResult)
    {
        if(numbers.Length == currentIndex) 
        {
            if(currentResult == target) count++;
            return;
        }
        DFS(numbers, target, currentIndex + 1, currentResult + numbers[currentIndex]);
        DFS(numbers, target, currentIndex + 1,currentResult - numbers[currentIndex]);
    }
    
    public int solution(int[] numbers, int target) 
    {
        DFS(numbers, target, 0, 0);
        return count;
    }
}

 

위와 같은 코드를 작성하면서 함수의 반환형을 void 타입으로 줬는데

 

return 을 사용한 이유는 return 반환 뿐만 아니라 함수의 종료의 의미도 가지기 때문이다.

 

따라서, return을 통해 조건에 부합하는 경우 아래 코드가 실행되지 않도록 했다.

 

=> 하지만, 위의 코드를 작성하고 if - else를 사용하면 된다는 사실을 눈치 챘다... ㅎㅎ;;

 

using System;

public class Solution {

    //결과를 개수 변수
    public int count = 0;
    
    //필요한 매개변수
    //숫자 배열
    //타겟 넘버
    //현재 index
    //현재 숫자 결과
    public void DFS(int[] numbers, int target, int currentIndex, int currentResult)
    {
        if(numbers.Length == currentIndex) 
        {
            if(currentResult == target) count++;
        }
        else
        {
            DFS(numbers, target, currentIndex + 1, currentResult + numbers[currentIndex]);
            DFS(numbers, target, currentIndex + 1,currentResult - numbers[currentIndex]);   
        }
    }
    
    public int solution(int[] numbers, int target) 
    {
        DFS(numbers, target, 0, 0);
        return count;
    }
}