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

프로그래머스

 

풀이

 

1. 왜 DFS를 사용했는가

[코테 대비] BFS/DFS 정리 + 차이점

단순히 +, - 분기처리를 통해 완전탐색을 해야하기 때문에 DFS를 사용했다.

BFS로 처리할 수도 있겠지만, 깊이를 활용해서 depth가 배열의 길이만큼이 된다면 다 찾은 것이고, 그리고 재귀함수를 통해 구현하면 더 간단하게 구현할 수 있을 거라 생각했기 때문이다. 특히 모든 경로를 탐색해야하고, 하나의 노드에서 마지막 레벨까지 탐색한 뒤에 해당 누적 합을 알아야 하기 때문에 DFS가 적절하다고 생각했다.

 

BFS로 짠 코드보다 DFS로 짠 코드가 메모리는 비슷하지만, 작동 시간은 더 빨랐다. 이유가 뭘지 생각해봤는데, BFS는 얕은 곳에서 정답이 나오면 더 효율적인 방법인데, 이 문제의 경우 끝까지 확인을 해야하기 때문이 아닐까..?

 

다른 분의 블로그를 보고 노드-엣지로 구성된 그래프를 그릴 수 있는 문제나, 상하좌우로 움직이는 문제 뿐만이 아니라 이진 트리 형식으로 뻗어나갈 수 있는 문제는 DFS/BFS로 접근할 수 있다는 사실을 알게 되었다. 이 문제에서는 +와 - 부호에 따라 2가지 경우의 수가 생겨나기 때문에, 분기마다 2가지 경우로 자손이 생기게 된다.

 

 

처음 1번 노드는 0에서 시작해, 2번 노드 = 1번노드 - numbers[0] / 3번 노드 = 1번 노드 + numbers[0] 으로 계속해서 뻗어나가는 구조이다. 즉, 이진 트리 형식으로 뻗어나갈 수 있는 문제는 DFS/BFS로 접근할 수 있다 !

 

 

2. 다른 사람들은 코드를 어떻게 짰는가

다른 사람들의 코드를 보고 놀랐던 부분은 이걸 DP(동적프로그래밍)로 해결한 케이스가 있다는 것이다!

BFS로도 해결한 케이스가 있어서, 아래 코드에 BFS/DFS/DP 세 가지 유형으로 해결한 케이스를 전부 올렸으니 참고해주세요 😉

 

static int DFS(int sum, int[] numbers, int k, int target){
        if(k == numbers.length){
            if(sum == target){
                return 1;
            }
         return 0;
     }
     return DFS(sum + numbers[k], numbers, k+1, target) + DFS(sum - numbers[k], numbers, k+1, target);            
}

 

⏏ 점화식처럼 DFS retrun 값을 지정해준 사람도 있었다.

 

 

 

3. 시간복잡도와 공간복잡도

[Algorithm] DFS, BFS 시간복잡도가 O(N+E)인 이유

 

전체코드

 

DFS

import java.io.*;
import java.util.*;

class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        DFS(0, numbers, 0, target);
        return answer;
    }
    static void DFS(int sum, int[] numbers, int k, int target){
        if(k == numbers.length){
            if(sum == target){
                answer++;
            }
            return;
        }
        DFS(sum + numbers[k], numbers, k+1, target);
        DFS(sum - numbers[k], numbers, k+1, target);            
    }
}

 

BFS

import java.io.*;
import java.util.*;

class Solution {
    static class Node{
        int sum;
        int idx;
        Node(int sum, int idx){
            this.sum = sum;
            this.idx = idx;
        }
    }
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        BFS(numbers, target);
        return answer;
    }
    static void BFS(int[] numbers, int target){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0));
        
        while(!queue.isEmpty()){
            Node n = queue.poll();
            if(n.idx == numbers.length){
                if(n.sum == target){
                    answer++;
                }
                continue;
            }

            queue.add(new Node(n.sum+numbers[n.idx], n.idx+1));
            queue.add(new Node(n.sum-numbers[n.idx], n.idx+1));
        }
    }
}

 

DP

import java.io.*;
import java.util.*;

class Solution {
    static int dp[] = new int[2001];
    public int solution(int[] numbers, int target) {
        DP(numbers, target);
        return dp[target + 1000];
    }
    static void DP(int[] numbers, int target){
        dp[1000] = 1;
        for(int i=1; i<=numbers.length; i++){
            int nextDp[] = new int[2001];
            for(int j=0; j<= 2000; j++){
                if(dp[j] != 0){
                    nextDp[j + numbers[i - 1]] += dp[j];
                    nextDp[j - numbers[i - 1]] += dp[j];
                }
            }
            dp = nextDp;
        }
    }
}