[Programmers] 타겟 넘버 DFS 풀이, BFS 풀이 (Java)

타겟 넘버 

숫자 배열이 주어지고, 각각을 더하거나 빼서 target 을 만들 수 있는 모든 경우의 수를 구하는 문제였다. 자바로 풀었다.

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

DFS 풀이

재귀로 모든 경우의 수(더하고, 빼고) 로 다 넣어서 구한다. 만들어진 최종 값이 target 과 동일할 경우 1을 리턴하고 이 값을 누적한 것이 결과 값이다.

class Solution {

    public int dfs(int prev, int index, int[] numbers, int target) {

        if (index >= numbers.length) {
            if (target == prev) {
                return 1;
            }
            return 0;
        }

        int cur1 = prev + numbers[index];
        int cur2 = prev - numbers[index];

        int ans = 0;
        ans += dfs(cur1, index+1, numbers, target);
        ans += dfs(cur2, index+1, numbers, target);

        return ans;

    }

    public int solution(int[] numbers, int target) {
        int current = numbers[0];
        int answer = 0;
        answer += dfs(current, 1, numbers, target);
        answer += dfs(-current, 1, numbers, target);
        return answer;
    }
}

BFS 풀이

dfs 를 while 문으로 풀어 쓴 것이다. 자바에서는 튜플이 없길래 (ㅠㅠ) Pair 를 임시로 만들어주고, 현재 값과 참조했던 numbers 의 인덱스 값을 넣어주었다. (index 가 depth 개념)

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

class Solution {
    
    class Pair {
        int cur;
        int index;
        
        Pair(int cur, int index) {
            this.cur = cur;
            this.index = index;
        }
    }
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(numbers[0], 0));
        queue.offer(new Pair(-numbers[0], 0));

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            if (p.index == numbers.length-1) {
                if (p.cur == target) {
                    answer += 1;
                }
                continue;
            }
            int c1 = p.cur + numbers[p.index+1];
            int c2 = p.cur - numbers[p.index+1];
            
            queue.add(new Pair(c1, p.index+1));
            queue.add(new Pair(c2, p.index+1));
        }

        return answer;
    }
}

주저리

프로그래머스 문제는 첨 풀어봤는데, 표준 입/출력 이 없어서 너무 좋았다! 이래서 다들 프로그래머스에서 코딩 테스트 하나 싶기도.