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

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

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

 

 

[DFS 풀이 - 재귀]

// 재귀풀이
class Solution {
    static int cnt=0;
    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        return cnt;
    }
    
    static void dfs(int idx, int sum, int[] numbers, int target){
        if(idx == numbers.length){
            if(sum == target) cnt++;
            return;
        }

        dfs(idx+1, sum + numbers[idx], numbers, target);
        dfs(idx+1, sum - numbers[idx], numbers, target);
    }
}

 

[BFS 풀이 - 큐]

// bfs풀이
import java.util.*;
class Solution {
    static Queue<int[]> q = new LinkedList<>();
    public int solution(int[] numbers, int target) {
        int answer = 0;
        q.offer(new int[] {numbers[0], 0}); // '+' 로 시작
        q.offer(new int[] {-1 * numbers[0], 0}); // '-' 로 시작
        
        while(!q.isEmpty()){
            int num = q.peek()[0];
            int idx = q.peek()[1];
            q.poll();
            idx += 1;
            
            if(idx < numbers.length){ 
                q.offer(new int[] {num + numbers[idx], idx});
                q.offer(new int[] {num + (-1 * numbers[idx]), idx});
            }
            
            if(idx == numbers.length){
                if(num == target) answer++;
            }
        }
        
        return answer;
    }
}

 

• DFS, BFS로 풀어보았고 탐색 문제를 연습하기 좋은 문제였다.