[프로그래머스] (java) 타겟넘버 (BFS, DFS)
문제 설명
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 | return |
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
설명
n개의 음이 아닌 정수가 주어지고 target 정수가 주어지는데, 이 n개의 정수들의 합과 차의 여러 조합중에서 target을 만족하는 경우가 몇개인지 세야 한다. 핵심은 각각의 정수가 +, -로 변할 수 있으며 순서는 변하지 않는다는 것이다. 따라서 경우의 수만 따지자면, 모든 정수 합의 경우는 n개의 정수가 +, -로 구분되는 2가지 경우가 있으니 총 2^n개가 나온다.
이를 단순하게 이진 트리로 만들어본다면 다음 그림과 같다.
즉 트리를 탐색하면 답을 구할 수 있다.
첫번째 풀이 : DFS
첫 노드에서부터 시작해 마지막 노드까지 쭉 타고내려가며 깊이 우선 탐색을 하면서 각 노드를 더하거나 빼면 경우가 각각 나오므로 각 경우를 target과 비교하면 된다.
class Solution {
int count = 0;
public int solution(int[] numbers, int target) {
dfs(numbers, target, 0, 0);
return count;
}
private int dfs(int[] numbers, int target, int index, int sum) {
if (index == numbers.length) { // 마지막 leaf까지 진행했을 때
if(sum == target){
count++;
}
}
// 현재 숫자를 더하는 경우와 빼는 경우 두 가지 탐색
return dfs(numbers, target, index + 1, sum + numbers[index])
+ dfs(numbers, target, index + 1, sum - numbers[index]);
}
}
두번째 풀이 : BFS
큐는 (현재까지 사용한 숫자의 개수(level), 현재 합)으로 구성된다.
초기 상태는 (0,0)으로 시작하는 것으로 가정한다.
알아듣기 쉽도록 각 단계 코드의 흐름을 쪼개어 적어보자면
| 단계 | 큐의 상태 | 설명 |
| 0 | [(0,0)] | 초기 상태 |
| 1 | [(1,4), (1,-4)] | level 1 노드의 4를 더한 결과와 뺀 결과 |
| 2 | [(2,5), (2,3), (2,-3), (2,-5)] | level 2 노드의 1를 더한 결과와 뺀 결과 |
| 3 | [(3,7), (3,3), (3,5), (3,1), (3,-1), (3,-5), (3,-3), (3,-7)] | level 3 노드의 2를 더한 결과와 뺀 결과 |
| 4 | [(4,8), (4,6), (4,4), (4,2), (4,6), (4,4), (4,2), (4,0), (4,0), (4,-2), (4,-4), (4,-6), (4,-2), (4,-4), (4,-6), (4,-8)] | level 4 노드의 1를 더한 결과와 뺀 결과 |
즉 모든 단계를 진행한 후(= 현재까지 사용한 숫자의 개수 == numbers.length)
큐의 현재 합 부분이 target 과 일치하는 경우를 세면 될 것이다.
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int solution(int[] numbers, int target) {
Queue<int[]> queue = new LinkedList<>(); // java에서 queue 선언하기
queue.offer(new int[]{0, 0}); // {현재 인덱스, 현재 합}
int count = 0;
while (!queue.isEmpty()) {
int[] node = queue.poll();
int index = node[0];
int sum = node[1];
if (index == numbers.length) { // 모든 숫자를 사용한 경우
if (sum == target) count++;
} else {
queue.offer(new int[]{index + 1, sum + numbers[index]}); // 더하는 경우
queue.offer(new int[]{index + 1, sum - numbers[index]}); // 빼는 경우
}
}
return count;
}
}
DFS 쪽이 연상이나 구현이나 더 간단했던 것 같다.