타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다.
이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때
숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

풀이

public class TargetNumberFinder
{
    private static int _targetNumber;
    private static int _targetNumberCount = 0;
    private static int[] _numbers = null!;
    
    public static int Solution(int[] numbers, int target)
    {
        _targetNumber = target;
        _numbers = numbers;
        CalculateTargetNumber(0,0);
        return _targetNumberCount;
    }

    private static void CalculateTargetNumber(int startIndex, int number)
    {
        if (startIndex >= _numbers.Length)
        {
            if (number == _targetNumber)
            {
                _targetNumberCount++;
            }
                
            
            return;
        }
        int nextIndex = startIndex + 1;
        int nextNumberPositive = number + _numbers[startIndex];
        int nextNumberNegative = number - _numbers[startIndex];
        
        CalculateTargetNumber(nextIndex, nextNumberPositive);
        CalculateTargetNumber(nextIndex, nextNumberNegative);
    }
}

전역 변수

    private static int _targetNumber;
    private static int _targetNumberCount = 0;
    private static int[] _numbers = null!;

• Solution함수 뿐만 아니라 재귀 함수인 CalculateTargetNumber에서도 접근해야 하는 요소들을 전역 변수로 만들어 줌
• 찾고자 하는 목표 숫자를 _targetNumber, 현재까지 _targetNumber를 만드는 방법의 수를 확인하고자 _targetNumberCount를 추가하였고 주어진 정수 배열을 _numbers로 선언

재귀 함수

    private static void CalculateTargetNumber(int startIndex, int number)
    {
        if (startIndex >= _numbers.Length)
        {
            if (number == _targetNumber)
            {
                _targetNumberCount++;
            }
                
            
            return;
        }
        int nextIndex = startIndex + 1;
        int nextNumberPositive = number + _numbers[startIndex];
        int nextNumberNegative = number - _numbers[startIndex];
        
        CalculateTargetNumber(nextIndex, nextNumberPositive);
        CalculateTargetNumber(nextIndex, nextNumberNegative);
    }

• _numbers에 주어진 모든 숫자를 전부 + 또는 - 연산을 각각 실시했을 때 어떤 조합이 _targetNumber를 만드는지 확인하도록 재귀 함수를 작성
• 확인하고자 하는 시작 인덱스가 주어진 _numbers 길이를 초과한다면 재귀를 멈추고 해당 과정을 통해 만들어진 숫자가 _targetNumber와 같은지 확인하여 _targetNumberCount를 조작
• 모든 숫자에 대해서 +,-를 기준으로 하는 분기가 발생하므로 가장 깊은 가지까지 탐색 후 빠져 나오면서 연속적으로 다른 가지를 탐색

조건 설정

_numbers = [1, 1, 1, 1, 1]
_targetNumber = 3

재귀 함수 탐색 순서

1) +1+1+1+1+1 노드를 탐색. 배열의 끝에 도달했으므로
연산으로 만들어진 숫자를 확인 후 +1+1+1+1 노드로 회귀
2) +1+1+1+1-1 노드를 탐색. 배열의 끝에 도달했으므로
연산으로 만들어진 숫자를 확인 후 +1+1+1+1 노드로 회귀
3) +1+1+1+1 노드에서 다음 노드를 모두 확인했으므로
+1+1+1 노드로 회귀
4) +1+1+1-1 노드로 진행하여
+1+1+1-1+1 노드와 +1+1+1-1-1 노드에 대한 탐색 진행
...

• 위와 같은 탐색이 반복되며 모든 가능한 연산을 확인해 _targetNumber를 만드는 방법의 수를 확인 가능