[프로그래머스] 타겟 넘버(JAVA) 풀이

타겟 넘버

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

🚨모든 가능한 조합을 탐색해서 target에 도달하는 경우의 수 세는 문제 

→ 어떤 방식으로 모든 조합을 탐색할 수 있을까?

 

✅ 문제 풀이

[문제 탐색]

• 숫자 배열 각 원소에 대해 가능한 선택 : 2가지
• 총 n개의 숫자가 있을 때, 모든 가능한 경우의 수 : 2^n가지
• 모든 경로를 따라가며 누적합을 구하는 방식 : DFS 사용
  

1. 루트 노드(초기 합 0) 에서 시작
2. 각 레벨마다 숫자 하나씩 선택하며 + or - 붙여서 내려감
3. 마지막 레벨까지 내려갔을 때 누적된 합을 계산해 target과 비교
4. target이 아니면 다시 되돌아가서 탐색 → 재귀함수로 구현

 

 

 

 

[코드 설계]

1. 루트 노드부터 탐색 시작
2. 재귀 인자로 다음 인덱스 값(idx+1)과 누적 합(currentSum)을 넘겨줌
3. 재귀 시, 누적 합에서 숫자마다 +/- 두 가지로 분기 처리
   • dfs(idx+1, currentSum + staticNum[idx]);
     dfs(idx+1, currentSum - staticNum[idx]);
4. 인덱스(idx)가 마지막 노드(numbers.length) 이면 탐색 종료
5. 현재까지 누적된 합(currentSum) 이 target이면 정답 카운트 증가

[가능한 시간복잡도]

완전탐색(재귀/DFS) 패턴으로 모든 가능한 경우의 수 : 2^n가지

DFS는 이 모든 경로를 한 번씩 방문함 

=> 전체 시간복잡도 O(2^n) (문제에서 주어진 n의 범위는 20이하이기 때문에 2^20 = 1,048,576 이므로 1초 안에 무난히 처리됨)

 

✅풀이 코드

class Solution {
    static int[] staticNum;
    static int staticTarget;
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        staticNum = numbers;
        staticTarget = target;
        
        dfs(0,0);
        
        return answer;
    }
    
    static void dfs(int idx, int currentSum) {
        if(staticNum.length == idx){
            if(currentSum == staticTarget){
                answer++;
            }
            return;
        }
        
        dfs(idx+1, currentSum + staticNum[idx]);
        dfs(idx+1, currentSum - staticNum[idx]);
    }
}