programmers) 타겟 넘버, 재귀 연습하기

프로그래머스 타겟 넘버 Java 풀이 기록

DFS/BFS 개념을 공부한 뒤, 프로그래머스 타겟 넘버 문제를 풀어보았다.

이번에는 30분을 잡고 문제를 풀었지만, 시간 안에 풀이를 완성하지 못했다.
문제 설명을 아예 이해하지 못한 것은 아니었다. 오히려 “각 숫자마다 + 또는 - 두 갈래로 경우의 수가 나누어진다”는 점까지는 이해했다.

하지만 문제는 그다음이었다.
머릿속으로는 트리처럼 가지가 나뉘는 구조가 그려졌는데, 이걸 Java 코드로 어떻게 옮겨야 할지 감이 잘 오지 않았다.

특히 두 가지 갈래로 나누어지는 부분을 for문 안에서 구현해야 하는지, 아니면 dfs() 메서드 안에서 구현해야 하는지 헷갈렸다.
결국 생각은 어느 정도 했지만, 그 생각을 코드로 표현하는 단계에서 막힌 문제였다.

---

문제 풀이 정보

문제	프로그래머스 타겟 넘버
유형	DFS / 완전탐색
사용 언어	Java
풀이 시간	30분
결과	시간 내 풀이 실패
주요 원인	경우의 수가 나뉘는 구조를 DFS 코드로 옮기지 못함

---

문제 이해

타겟 넘버 문제는 배열 numbers가 주어졌을 때, 각 숫자 앞에 + 또는 -를 붙여서 target을 만드는 방법의 수를 구하는 문제다.

예를 들어 다음과 같은 입력이 있다고 하자.

numbers = [1, 1, 1, 1, 1]
target = 3

각 숫자마다 더하거나 빼는 선택을 할 수 있다.

+1 +1 +1 +1 +1 = 5
+1 +1 +1 +1 -1 = 3
+1 +1 +1 -1 +1 = 3
...

즉, 이 문제는 하나의 값을 구하는 문제가 아니라, target을 만들 수 있는 경우의 수를 세는 문제다.

핵심은 다음과 같다.

각 숫자마다 +를 붙이는 경우
각 숫자마다 -를 붙이는 경우
두 가지를 모두 탐색한다

---

처음 떠올린 생각

문제를 읽고 처음 떠올린 이미지는 트리 구조였다.

각 숫자마다 선택지가 두 개씩 생긴다.

현재 숫자를 더하는 경우
현재 숫자를 빼는 경우

예를 들어 numbers = [1, 2, 1]이라면 이런 식으로 경우의 수가 나뉜다.

시작 sum = 0
├── +1
│   ├── +2
│   │   ├── +1
│   │   └── -1
│   └── -2
│       ├── +1
│       └── -1
└── -1
    ├── +2
    │   ├── +1
    │   └── -1
    └── -2
        ├── +1
        └── -1

이렇게 보면 분명히 모든 경우의 수를 끝까지 확인해야 하는 문제라는 생각은 들었다.

그래서 BFS처럼 가까운 곳부터 최단 거리를 찾는 문제가 아니라,
한 경로를 끝까지 내려가며 모든 조합을 만들어보는 DFS에 가깝다는 것도 이해했다.

하지만 막상 코드로 쓰려고 하니 여기서 멈췄다.

이 두 갈래를 for문 안에서 만들어야 하나?
dfs 메서드 안에서 만들어야 하나?
sum을 어떻게 넘겨야 하지?
dfs는 값을 반환해야 하나?
answer는 어디서 증가시켜야 하지?

이 부분이 가장 어려웠다.

---

내가 처음 작성한 코드

처음에는 Stack을 사용해서 숫자를 하나씩 꺼내고, 꺼낸 숫자에 +, -를 적용하는 방식으로 접근했다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Stack<Integer> st = new Stack<>(Arrays.asList(nubmers));
        
        int start = st.poll;
        for (int num : st) {            
            if (dfs(num * -1, start) == target)
            if (dfs(numm, start *-1))
        }        
    
    }
    
    public int dfs(int num, Stack<Integer> st, sum) {
        if (st.isEmpty())
            return num      
        } else {
            sum1 += dfs(num * -1, sum);             
            sum2 += dfs(num, sum);  
        }
        
    }
}

지금 다시 보면 문법적으로도 완성되지 않은 코드다.
하지만 당시에는 “숫자를 하나씩 꺼내서 더하거나 빼면 되지 않을까?”라고 생각했다.

즉, 방향은 완전히 틀린 것은 아니었지만, 그 생각을 코드로 옮기는 방식이 잘못됐다.

---

왜 못 풀었는가?

이번 문제를 못 푼 가장 큰 이유는 내 생각을 코드 구조로 옮기는 것이 아직 익숙하지 않았기 때문이다.

문제를 보면서 두 가지 갈래로 경우의 수가 나누어지는 것은 이해했다.
+를 선택하는 경우와 -를 선택하는 경우가 있고, 이 선택이 숫자 개수만큼 반복되면서 트리처럼 뻗어나간다는 것도 알았다.

하지만 이 갈래를 코드에서 어디에 표현해야 할지 감이 잡히지 않았다.

처음에는 이런 고민을 했다.

고민한 부분헷갈렸던 이유

두 갈래를 for문 안에서 만들어야 하나?	배열을 순회해야 한다고 생각해서 반복문을 먼저 떠올림
두 갈래를 dfs() 안에서 만들어야 하나?	DFS가 재귀라는 건 알지만 호출 구조가 익숙하지 않았음
sum은 어디서 계산해야 하나?	메서드 안에서 계산할지, 인자로 넘길지 헷갈림
dfs()는 값을 반환해야 하나?	경우의 수를 세는 문제라 반환값 구조가 애매하게 느껴짐
answer는 언제 증가시키나?	모든 숫자를 다 쓴 뒤 비교해야 한다는 구조가 바로 떠오르지 않음

정리해보면, 트리 구조로 경우의 수가 나뉜다는 생각은 했지만
그 트리의 한 갈래를 코드에서는 아래처럼 표현한다는 것을 떠올리지 못했다.

dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);

즉, 두 갈래로 나뉘는 부분은 for문 안에서 억지로 만드는 것이 아니라,
dfs 메서드 안에서 재귀 호출을 두 번 하는 방식으로 표현하는 것이었다.

이 부분을 바로 떠올리지 못해서 풀이가 막혔다.

---

시간이 부족했는가?

30분 안에 풀이를 완성하지 못했기 때문에 시간도 부족했다.

하지만 단순히 시간이 모자랐다기보다는, 초반에 구현 방향을 잡지 못하면서 시간이 많이 흘렀다.

문제 해석에는 어느 정도 도달했지만, 아래 단계에서 시간이 오래 걸렸다.

트리 구조로 경우의 수가 나뉜다
→ 그런데 이걸 코드에서 어떻게 표현하지?
→ 반복문인가?
→ Stack인가?
→ dfs의 반환값은 뭘까?

결국 시간 부족의 원인은 알고리즘 개념을 코드 구조로 바꾸는 과정이 아직 익숙하지 않았기 때문이었다.

---

문제 해석을 잘못했는가?

문제 해석을 완전히 잘못한 것은 아니었다.

각 숫자마다 + 또는 -를 붙여야 한다는 점은 이해했다.
그리고 모든 경우의 수를 확인해야 한다는 점도 어느 정도 파악했다.

다만 중요한 구현 포인트를 놓쳤다.

모든 숫자를 다 사용한 뒤에만 target과 비교해야 한다.

중간에 sum이 target과 같아졌다고 바로 정답으로 세면 안 된다.
모든 숫자는 반드시 한 번씩 사용해야 하기 때문이다.

그래서 정확한 문제 해석은 다음과 같다.

각 숫자는 반드시 한 번씩 사용한다.
각 숫자마다 + 또는 - 중 하나를 선택한다.
모든 숫자를 다 사용한 뒤 target과 비교한다.
target과 같으면 경우의 수를 1 증가시킨다.

---

자료구조 선택을 잘못했는가?

이번 풀이에서는 Stack을 사용하려고 했다.
DFS를 공부하면서 “DFS는 Stack 또는 재귀를 사용한다”는 말을 봤기 때문에 Stack을 먼저 떠올렸다.

하지만 이 문제에서는 Stack을 직접 사용할 필요가 없었다.

자료구조필요 여부이유

Stack	불필요	숫자를 꺼내는 구조보다 인덱스 기반 DFS가 더 자연스러움
Queue	불필요	최단 거리나 가까운 곳부터 탐색하는 문제가 아님
PriorityQueue	불필요	우선순위가 필요한 문제가 아님
배열	필요	입력값 numbers를 순서대로 탐색
DFS 재귀	필요	+, - 모든 경우를 탐색해야 함

이 문제는 Stack 자료구조를 직접 다루는 문제가 아니라,
배열의 index를 하나씩 이동하면서 현재까지의 sum을 넘기는 재귀 문제였다.

---

구현 실수가 있었는가?

구현 실수도 있었다.
처음 작성한 코드는 아이디어를 코드로 옮기는 중간 단계에 가까웠고, Java 문법적으로도 여러 문제가 있었다.

코드문제점

return answer;	메서드 초반에 있어 아래 코드가 실행되지 않음
nubmers	numbers 오타
Arrays.asList(numbers)	int[]는 바로 List<Integer>로 변환되지 않음
st.poll	Stack에는 poll 메서드가 없음
numm	변수명 오타
sum	타입이 선언되지 않음
dfs()	반환값과 역할이 명확하지 않음

특히 이 부분이 가장 큰 구현 실수였다.

return answer;

메서드 초반에 return이 있으면 그 아래 코드는 실행되지 않는다.
즉, 이후에 어떤 로직을 작성해도 실제로는 도달할 수 없다.

하지만 이번 실패의 핵심은 단순 문법 실수라기보다,
DFS 구조를 명확히 잡기 전에 코드를 작성하려고 했던 것이다.

---

엣지 케이스를 놓쳤는가?

이번에는 구현 자체가 완성되지 않았기 때문에 엣지 케이스를 검토하는 단계까지 가지 못했다.

하지만 다시 풀 때는 아래 케이스를 확인해야 한다.

케이스예시확인할 점

기본 예시	[1,1,1,1,1], target 3	정답이 5인지
숫자가 하나인 경우	[1], target 1	+1인 경우만 정답
target이 음수인 경우	[1,2,3], target -2	음수 누적합 처리 가능 여부
정답이 없는 경우	[1,2,3], target 100	0을 반환하는지
중간에 target이 되는 경우	[1,2,3], target 1	모든 숫자를 다 쓴 뒤 비교하는지

특히 주의할 부분은 이거다.

중간에 sum이 target과 같아져도 정답이 아니다.
모든 숫자를 다 사용한 뒤 target과 같아야 정답이다.

---

예외 케이스 때문에 일부 테스트가 실패했는가?

이번에는 특정 예외 케이스 때문에 일부 테스트가 실패한 상황은 아니었다.
코드가 완성되지 않았기 때문에 테스트 통과 여부를 확인하기 전 단계에서 막혔다.

즉, 이번 실패는 예외 케이스 누락보다는 기본 DFS 구조 구현 실패에 가깝다.

만약 코드가 어느 정도 완성된 뒤 실패했다면 다음 케이스를 의심했을 것 같다.

실패 가능 케이스원인

target이 음수인 경우	누적합이 음수가 되는 상황을 고려하지 않음
정답이 0인 경우	경우의 수가 없을 때 처리 누락
숫자를 다 쓰기 전에 target과 비교	잘못된 시점에 answer 증가
전역 sum을 직접 변경	재귀 호출 간 값이 섞일 수 있음

---

시간복잡도와 공간복잡도

타겟 넘버 문제는 각 숫자마다 두 가지 선택지가 있다.

+를 붙이는 경우
-를 붙이는 경우

숫자가 N개라면 가능한 경우의 수는 다음과 같다.

2 × 2 × 2 × ... × 2 = 2^N

따라서 시간복잡도는 다음과 같다.

시간복잡도: O(2^N)

공간복잡도는 재귀 호출 깊이를 기준으로 생각할 수 있다.
숫자가 N개라면 재귀도 최대 N 깊이까지 들어간다.

공간복잡도: O(N)

정리하면 다음과 같다.

구분복잡도이유

시간복잡도	O(2^N)	각 숫자마다 +, - 두 가지 선택
공간복잡도	O(N)	재귀 호출 깊이가 최대 N

이번에는 시간복잡도 판단을 제대로 해서 풀이를 선택했다기보다는,
트리 구조로 모든 경우의 수가 나뉜다는 직관만 있었다.

다시 정리해보니 이 문제는 O(2^N) 완전탐색 문제이고, 입력 크기가 크지 않기 때문에 DFS로 풀 수 있는 문제였다.

즉, 시간복잡도를 잘못 판단해서 실패한 것은 아니지만,
처음 풀이 중에는 시간복잡도까지 명확하게 정리하지 못했다.

---

재귀에서 새롭게 이해한 점

이번 문제를 복습하면서 가장 크게 이해한 부분은 이것이다.

처음에는 메서드 안에서 값을 계산하고, 그 결과를 변수에 저장한 뒤 다시 넘겨야 한다고 생각했다.

하지만 타겟 넘버 DFS에서는 계산된 값을 다음 재귀 호출의 인자로 넘기면 된다.

핵심 구조는 다음과 같다.

dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);

처음에는 이 코드가 낯설었지만, 변수로 풀어 쓰면 훨씬 이해가 쉬웠다.

int currentNumber = numbers[index];

int plusSum = sum + currentNumber;
int minusSum = sum - currentNumber;

dfs(index + 1, plusSum);
dfs(index + 1, minusSum);

이렇게 보면 흐름이 명확하다.

현재 숫자를 꺼낸다.
더한 결과를 만든다.
뺀 결과를 만든다.
각각 다음 DFS로 넘긴다.

즉, 재귀는 메서드 안에서 모든 계산을 끝내는 것이 아니라,
현재 상태를 다음 호출에게 넘기면서 경우를 나누는 방식이었다.

---

올바른 DFS 풀이

정리한 뒤 다시 보면, 타겟 넘버 문제는 다음과 같이 풀 수 있다.

class Solution {
    int answer = 0;
    // int tartget = 0; 타겟을 인스턴스 변수로 선언하여 사용 할 수도 있음.

    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }

    public void dfs(int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }

        int currentNumber = numbers[index];

        int plusSum = sum + currentNumber;
        int minusSum = sum - currentNumber;

        dfs(numbers, target, index + 1, plusSum);
        dfs(numbers, target, index + 1, minusSum);
    }
}

---

코드 흐름 이해하기

예를 들어 다음 입력을 생각해보자.

numbers = [1, 2]
target = 3

처음 시작은 다음과 같다.

dfs(0, 0)

의미는 다음과 같다.

0번째 숫자를 처리할 차례이고,
현재까지의 합은 0이다.

0번째 숫자 1을 더하거나 뺀다.

dfs(0, 0)
├── dfs(1, 1)   // +1
└── dfs(1, -1)  // -1

그다음 1번째 숫자 2를 더하거나 뺀다.

dfs(0, 0)
├── dfs(1, 1)
│   ├── dfs(2, 3)    // +1 +2
│   └── dfs(2, -1)   // +1 -2
└── dfs(1, -1)
    ├── dfs(2, 1)    // -1 +2
    └── dfs(2, -3)   // -1 -2

index == numbers.length가 되면 모든 숫자를 다 사용한 상태다.
이때만 sum과 target을 비교한다.

dfs(2, 3)  → target과 같음 → answer++
dfs(2, -1) → 다름
dfs(2, 1)  → 다름
dfs(2, -3) → 다름

따라서 정답은 1이 된다.

---

다시 풀 때 주의할 점

다시 풀 때는 아래 순서로 접근해야겠다.

순서확인할 것

1	먼저 트리 구조로 경우의 수가 어떻게 나뉘는지 그려본다
2	DFS 함수가 들고 갈 상태를 정한다
3	index, sum을 매개변수로 둔다
4	종료 조건은 index == numbers.length로 잡는다
5	종료 시점에만 sum == target을 확인한다
6	두 갈래 분기는 dfs() 안에서 재귀 호출 두 번으로 표현한다
7	Stack 같은 자료구조부터 떠올리지 말고 선택 트리를 먼저 생각한다

이번 문제에서 내가 특히 기억해야 할 부분은 이것이다.

두 갈래로 나뉘는 선택은 for문이 아니라,
dfs 메서드 안에서 재귀 호출 두 번으로 표현할 수 있다.

---

이번 문제 회고 정리

항목회고

왜 못 풀었는가?	트리 구조는 이해했지만, 두 갈래 분기를 코드로 옮기는 데 어려움이 있었다
시간이 부족했는가?	30분 내 풀이 실패. 초반에 구현 방향을 못 잡아 시간이 부족했다
문제 해석을 잘못했는가?	큰 방향은 맞았다. 다만 모든 숫자를 다 사용한 뒤 target과 비교해야 한다는 구현 포인트가 부족했다
자료구조 선택을 잘못했는가?	Stack을 사용하려 했지만 이 문제에는 불필요했다
엣지 케이스를 놓쳤는가?	구현이 완성되지 않아 엣지 케이스 검토까지 가지 못했다
구현 실수가 있었는가?	return 위치, 오타, Stack 메서드 사용 등 문법적 실수가 있었다
시간복잡도 판단은?	풀이 중에는 명확히 못 했지만, 정리하면 O(2^N)이다
공간복잡도 판단은?	재귀 깊이 기준 O(N)이다
예외 케이스로 실패했는가?	특정 예외 케이스 실패가 아니라 기본 DFS 구조 구현 전 단계에서 막혔다

---

마무리

이번 타겟 넘버 문제는 DFS 입문 문제였지만, 오랜만에 재귀 문제를 풀어보니 생각보다 쉽지 않았다.

문제에서 요구하는 것은 단순했다.

각 숫자에 + 또는 -를 붙여 target이 되는 경우의 수 구하기

하지만 이걸 코드로 옮기려면 재귀 함수가 어떤 상태를 들고 가야 하는지 먼저 정해야 했다.

이번에 가장 크게 배운 점은 다음과 같다.

재귀는 메서드 안에서 모든 계산을 끝내는 것이 아니라,
현재 상태를 다음 호출의 인자로 넘기면서 경우를 나누는 방식이다.

타겟 넘버에서는 그 상태가 바로 index와 sum이었다.

index = 현재 몇 번째 숫자를 보고 있는지
sum = 지금까지 계산한 누적 합

그리고 두 갈래로 나뉘는 선택은 for문으로 억지로 만들기보다,
dfs() 안에서 재귀 호출을 두 번 하는 방식으로 표현할 수 있었다.

dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);