[프로그래머스] 타겟 넘버 자바

문제

 

코딩테스트 연습 - 타겟 넘버

 

문제 풀이

 

DFS/BFS 문제를 풀고 싶어서 DFS카테고리에서 문제를 골랐는데, 아무리 생각해도 완전탐색으로 푸는 것 같았다. 

그래서 찾아보니 DFS(또는 BFS)는 모든 노드를 탐색하는 것을 목표로 하는 완전탐색을 기반으로 한 탐색 기법이라고 나왔다.

아마 완전탐색을 구현하는 방법 중 하나로 DFS/BFS가 포함되어 있나보다..? 

 

더하기, 빼기 연산밖에 하지 못하므로 주어진 숫자 배열에서 더할 숫자만 골라주면 나머지면 빼면 된다.

더할 숫자를 찾는 것은 조합으로 고르면 되겠다고 생각했다.

주어진 배열에서 (0~배열크기) 만큼 각각 숫자를 고르는 조합 함수를 적용했다.

조합 함수에서 방문된 숫자는 더하고 나머지는 빼기를 한 결과가 문제의 target넘버와 같을때마다 answer을 증가해주었다.

 

조합은 백트래킹이나 재귀를 사용하여 구현이 가능하다. 

조합을 뽑아낼 배열과, 조합에 뽑혔는지 체크하는 배열, 몇개에서 몇개뽑을지를 받아서 재귀 호출한다.

 

 

소스 코드

 

class Solution {
    static int answer = 0;
    static int target;
    
    public int solution(int[] numbers, int target2) {
        boolean[] visited = new boolean[numbers.length];
        target = target2;
        for(int i = 0; i <= numbers.length; i++)
            combination(numbers, visited, 0, numbers.length, i);
        return answer;
    }
    
    //조합
    public void combination(int[] arr, boolean[] visited, int depth, int n, int r){
        if(r == 0){
            int rslt = 0;
            for(int i = 0; i < arr.length; i++){
                if(visited[i])      //뽑힌거면
                    rslt += arr[i];  //더하고
                else
                    rslt -= arr[i];        
            }
            if(rslt == target)
                answer++;
            return;
        }
        
        if(depth == n)
            return;
        
        visited[depth] = true;
        combination(arr, visited, depth+1, n, r-1);
        
        visited[depth] = false;
        combination(arr, visited, depth+1, n, r);
    }
}