[프로그래머스] 타겟 넘버 (Lv.2)
문제 링크
문제 설명
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 이하인 자연수입니다.
내 풀이
각 숫자마다 더하거나 빼는 두 가지 선택지가 있으므로, 재귀 DFS로 모든 경우를 탐색했다.
dfs(idx, current)는 idx번째 숫자를 선택할 차례이고, 지금까지의 합이 current인 상태를 의미한다. 숫자를 더하는 방향과 빼는 방향으로 각각 재귀 호출해 트리 전체를 탐색하고, 마지막 숫자까지 선택했을 때 합이 target이면 카운트를 1 증가시킨다.
#include <string>
#include <vector>
using namespace std;
int count = 0;
vector<int> Numbers;
int Target;
void dfs(int idx, int current)
{
if(idx == Numbers.size())
{
if(current == Target) count++;
return;
}
dfs(idx + 1, current + Numbers[idx]);
dfs(idx + 1, current - Numbers[idx]);
}
int solution(vector<int> numbers, int target) {
count = 0;
Numbers = numbers;
Target = target;
dfs(0, 0);
return count;
}
시간복잡도 분석
각 숫자마다 + / - 두 가지 선택을 하므로, 숫자가 n개일 때 총 경우의 수는 2^n이다.
| 단계 | 시간복잡도 |
|---|---|
| DFS 전체 탐색 | O(2^N) |
제한사항에서 N ≤ 20이므로 2^20 = 약 100만 연산으로 충분히 통과 가능하다.
오답노트
오류: Segmentation Fault
// 수정 전
dfs(idx + 1, current + Numbers[idx]);
dfs(idx - 1, current - Numbers[idx]); // ← idx - 1이 잘못됨
// 수정 후
dfs(idx + 1, current + Numbers[idx]);
dfs(idx + 1, current - Numbers[idx]); // 방향(+/-)과 인덱스 이동은 별개
빼는 방향(-) 선택이어도 다음 숫자로 이동해야 한다. idx - 1로 작성하면 인덱스가 음수로 내려가며 무한 재귀 → 스택 오버플로우가 발생한다.
후기
문제를 이해하는 건 어렵지 않았지만, 처음에 코드로 옮기는 작업이 조금 어려웠다. 이런 문제들을 좀 많이 풀면서, 생각한 로직을 코드로 옮기는 것에 익숙해져야겠다.