프로그래머스 2단계 : 타겟 넘버 (Java 자바)

문제 설명

 

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 함수를 작성해주세요.

 

 

제한사항

 

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

 

 

 

풀이

 

숫자 배열 numbers와 타겟 숫자 target을 이용하여, 숫자를 더하거나 빼서 타겟 숫자를 만들 수 있는 방법의 수를 계산하는 문제입니다.

 

1. solution 메서드는 문제의 진입점입니다. numbers 배열과 target 값을 인자로 받아서 깊이 우선 탐색을 수행하는 dfs 메서드를 호출하고, 최종적으로 결과를 반환합니다.

 

2. dfs 메서드는 깊이 우선 탐색을 수행하는 재귀 함수입니다. 현재까지의 합 sum을 유지하며, idx 변수는 현재까지 사용한 숫자의 인덱스를 나타냅니다. 만약 idx가 numbers 배열의 길이와 같다면 모든 숫자를 다 사용한 것이므로, 현재까지의 합이 target과 같은지를 검사하고 결과를 업데이트합니다.

3. 재귀 호출은 두 가지 경우로 이루어집니다. 하나는 현재 숫자를 더하는 경우이고 다른 하나는 현재 숫자를 빼는 경우입니다. 이 두 가지 경우를 각각 재귀 호출하여 다음 숫자로 진행하게 됩니다.

4. answer 변수는 현재까지의 합이 target과 같은 경우를 세는 역할을 합니다. 가능한 모든 조합을 탐색하며 조건에 맞는 경우에만 answer가 증가하게 됩니다.

깊이 우선 탐색을 사용하여 가능한 모든 숫자 조합을 검사하고, 조건을 만족하는 경우의 수를 세는 방식으로 타겟 숫자를 만들 수 있는 방법의 수를 계산합니다.

 

class Solution {
    int answer = 0; // 타겟 숫자를 만들 수 있는 방법의 수를 저장하는 변수
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0); // 깊이 우선 탐색을 통해 숫자를 조합하여 타겟 숫자를 만드는 함수 호출
        return answer; // 결과 반환
    }

    public void dfs(int[] numbers, int target, int idx, int sum) {
        if (idx == numbers.length) { // 모든 숫자를 다 사용한 경우
            if (target == sum) // 현재까지의 합이 타겟 숫자와 같다면
                answer++; // 방법의 수를 하나 증가시킴
            return; // 함수 종료
        }
        
        // 현재 숫자를 더하는 경우와 빼는 경우를 각각 재귀적으로 탐색
        dfs(numbers, target, idx + 1, sum + numbers[idx]);
        dfs(numbers, target, idx + 1, sum - numbers[idx]);
    }
}