# \[99클럽 코테 스터디 34일차 TIL] 프로그래머스 - 타겟 넘버
## \[level 2] 타겟 넘버 - 43165
[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java)
#### 구분
코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS）
#### 문제 설명
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
```
* 총 2가지 방법이 있으므로, 2를 return 합니다.
***
## 풀이 코드
```java
class Solution {
private int cnt = 0;
private int[] sign = {1, -1};
public int solution(int[] numbers, int target) {
int len = numbers.length;
dfs(numbers, 0, 0, len, target);
return cnt;
}
private void dfs(int[] numbers, int depth, int ret, int len, int target) {
if (depth == len) {
if (ret == target) cnt++;
return;
}
for (int s : sign) {
int result = ret + numbers[depth] * s;
dfs(numbers, depth + 1, result, len, target);
}
}
}
```
* Time: 16.62 ms
* Memory: 83.4 MB
주어진 `numbers` 배열의 순서는 바뀌지 않고 모든 요소를 사용하여 `target` 숫자를 만들면 되는 문제다. `numbers` 배열의 요소를 `+` 또는 `-` 로 구분하여 하나하나 더해나가면 된다. 그림으로 그려보면 아래와 같다.
타겟 넘버 DFS
위 그림을 토대로 `depth` 가 배열의 길이와 동일하면 재귀를 끝내고 그때까지 더한 값이 `target` 값과 동일하면 `cnt` 를 증분한다. DFS 를 알고 있으면 쉽게 풀 수 있는 문제였다.
위 풀이 코드를 아래와 같이 조금 더 개선해봤다. 풀이 과정은 동일하고 반환 처리를 변경해봤다.
### 개선하기
```java
class Solution {
public int solution(int[] numbers, int target) {
int answer = dfs(numbers, 0, 0, target);
return answer;
}
private int dfs(int[] numbers, int depth, int sum, int target) {
if (depth == numbers.length) {
return sum == target ? 1 : 0;
}
return dfs(numbers, depth + 1, sum + numbers[depth], target) +
dfs(numbers, depth + 1, sum - numbers[depth], target);
}
}
```
* TIme: 4.37 ms
* Memory: 76.9 MB
처음 풀이에서는 각 요소의 음수와 양수를 구하기 위해 `int[] sign = {1, -1};` 을 이용했는데 그럴 필요 없이 각각 재귀 함수로 호출하는 방식으로 개선했고 성능도 개선됐다.
해당 문제를 BFS 로 푸는 방법은 감이 잡히질 않았는데 다른 사람의 풀이를 통해 알 수 있었다.
### 다른 사람의 풀이 - BFS
```java
import java.util.LinkedList;
import java.util.Queue;
class Solution {
Queue q = new LinkedList();
public int solution(int[] numbers, int target) {
int answer = 0;
q.offer(0);
q.offer(0);
while(q.peek() != null){
int depth =q.poll();
int sum = q.poll();
if(depth == numbers.length){
if(sum == target)
answer++;
}else {
q.offer(depth + 1);
q.offer(sum + numbers[depth]);
q.offer(depth + 1);
q.offer(sum - numbers[depth]);
}
}
return answer;
}
}
```
* Time: 254.52 ms
* Memory: 188 MB
성능은 DFS 보단 안좋지만 코드만 봤을 때는 더 직관적으로 이해되는 것 같다.
***
\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://devlee.gitbook.io/docs/study/99/99-34-til.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.