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

🙋🏻‍♀️ DFS 사용!

구현으로 풀 듯이 하려다가, 이게 DFS/BFS 유형인걸 알고 풀었기때문에 어떻게 사용될지를 생각해봤다.

금방 DFS 라는것은 알 수 있었으나, 재귀적으로 어떻게 호출해야할지 감이 안왔다.

내 풀이

class Solution {
    static int answer;
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);

        return answer;
    }
    
    public void dfs(int[] numbers, int target, int depth, int sum) {
        if(depth == numbers.length) {
            if(sum == target) answer++;
        } else {
            dfs(numbers, target, depth+1, sum+numbers[depth]);
            dfs(numbers, target, depth+1, sum-numbers[depth]);
        }
    }
}

• 깊이랑 합까지 파라미터로 넘긴다!
  (이 생각 전혀 못 함)

그리고 다른 풀이를 찾아봤다.

다른 풀이 1

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

• 전역변수를 사용하는 대신, 끝까지 탐색했을 때 1 or 0을 반환하며 재귀적으로 호출하는 즉시 합하는것도 엄청난 방법!

다른 풀이 2

Queue로도 가능하다

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    Queue<Integer> q = new LinkedList<Integer>();
    public int solution(int[] numbers, int target) {
        int answer = 0;
        q.offer(0);
        q.offer(0);
        while(q.peek()!=null){
            int level =q.poll();
            int v = q.poll();
            if(level==numbers.length){
                if(v==target)
                    answer++;
            }else {

                q.offer(level + 1);
                q.offer(v + numbers[level]);

                q.offer(level + 1);
                q.offer(v - numbers[level]);
            }
        }
        return answer;
    }   
}

• 큐에 깊이와 합을 넣고, 빼면서 체크!!