class Solution {
int answer;
public int solution(int[] numbers, int target) {
answer = 0;
dfs(numbers, target, 0, '+', 0);
dfs(numbers, target, 0, '-', 0);
return answer;
}
public void dfs(int[] numbers, int target, int sum, char ch, int idx) {
switch (ch) {
case '+':
sum += numbers[idx];
break;
case '-':
sum -= numbers[idx];
break;
}
if (idx == (numbers.length - 1)) {
if (sum == target) {
answer++;
}
} else {
dfs(numbers, target, sum, '+', idx + 1);
dfs(numbers, target, sum, '-', idx + 1);
}
}
}
재귀함수를 이용한 DFS 알고리즘으로 접근을 했다.
DFS를 이용해야겠다는 생각은 했지만 stack을 이용한 DFS로 처음에 접근했다.
약간의 힌트를 통해 재귀함수로 방향을 바꾸었으나, dfs
메소드 반환형을 int
로 해야한다는 강박에 return
조건을 어떻게 설정해야하나 고민했었다.
결국 다른 분의 코드를 참고하여 반환형을 void
로 바꾸고 idx
값 비교와 sum
값 비교를 통해 문제를 해결할 수 있었다.
핵심
- 재귀함수 반환형
void
idx
값이 배열 끝에 도달했을 때,sum
이target
과 같은지 비교
'Coding Test > Programmers' 카테고리의 다른 글
[Java] 완주하지 못한 선수 (0) | 2022.06.29 |
---|---|
[Java] 가장 큰수 (0) | 2022.06.29 |
[Java] 짝지어 제어하기 (0) | 2022.06.26 |
[Java] 기능개발 (0) | 2022.06.26 |
[Java] 카카오프렌즈 컬러링북 (0) | 2022.06.23 |