프로그래머스 알고리즘 고득점 Kit - [Lv.2] 타겟 넘버 (Java)

문제 출처 - 링크

알고리즘 분류

• 깊이/너비 우선 탐색(DFS/BFS)

📋 문제 요약 설명

• 숫자 배열의 값을 + 또는 - 를 붙여서 만든 조합을 계산한 합계가 target을 만드는 경우의 수를 찾아라

💡 알고리즘 설계 / 접근 방법

1. DFS를 사용한 풀이

   • 재귀 함수를 사용한 백트랙킹 방식을 사용한다.

     • 배열의 숫자마다 + 또는 - 를 계산하는 것을 재귀 함수를 통해 목표하는 합계가 나오는 조합을 찾는다.

   • DFS로 선택한 이유

     • 최단 경로를 찾는 문제가 아니고, 모든 가능한 조합을 찾는 문제라서 백트랙킹 방식으로 풀면 되겠다고 생각했다.

➕ 보완하기 / 성능 비교

• BFS 랑 DP 를 사용한 문제 풀이
  https://velog.io/@doxxx93/practice-kit-dfs-bfs-1

✅ 풀이

시간 복잡도 → O(2ⁿ)

• 모든 숫자를 한 번씩 사용하므로 깊이 = n
• 트리의 노드 수 = 2^n (완전 이진 트리)
  • 한 숫자마다 두 갈래 분기 → 이진 트리 탐색 구조 이다.

DFS 풀이 1 → 전역 변수 방식

// DFS 풀이 1 -> 전역 변수 방식
class Solution {  
    int count = 0;

    public int solution(int[] numbers, int target) {
        // 깊이, 숫자 배열, 목표 숫자, 현재 합계
        dfs(0, numbers, target, 0);
        return count;
    }

    private void dfs(int depth, int[] numbers, int target, int sum) {
        if (depth == numbers.length) { // 배열의 모든 숫자를 사용했을 때
            if (sum == target) { // 목표 숫자와 현재 합계가 같으면
                count++; // 유효한 조합이므로 1가지 방법을 찾았다.
            }
            return;
        }
        // 재귀 호출 (백트래킹) -> 매번 +, - 로 나눠지면서 모든 조합을 탐색함
        dfs(depth + 1, numbers, target, sum + numbers[depth]);
        dfs(depth + 1, numbers, target, sum - numbers[depth]);
    }
}

DFS 풀이 2 → 리턴값 누적 방식

// DFS 풀이 2 -> 리턴값 누적 방식
class Solution {    
    public int solution(int[] numbers, int target) {
        // 깊이, 숫자 배열, 목표 숫자, 현재 합계
        return dfs(0, numbers, target, 0); // 재귀 함수 호출
    }

    private int dfs(int depth, int[] numbers, int target, int sum) {
        if (depth == numbers.length) { // 배열의 모든 숫자를 사용했을 때
            if (sum == target) { // 목표 숫자와 현재 합계가 같으면
                return 1; // 유효한 조합이므로 1가지 방법을 찾아서 1을 반환
            }
            return 0; // 합계가 맞지 않으면 실패한 경로이므로 0을 반환
        }
        // 모든 경로에서 성공한 경우를 1씩 반환하고, 재귀적으로 + 연산하여 총 합을 리턴
        return dfs(depth + 1, numbers, target, sum + numbers[depth])
             + dfs(depth + 1, numbers, target, sum - numbers[depth]);
    }
}