[Java] 프로그래머스 Lv.2 : 타겟 넘버

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

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

 

풀이

DFS를 이용한 풀이

depth 변수 값을 통해 탐색 중인 트리의 깊이를 알 수 있다.

트리 끝에 도착했다면, 여태 계산한 result와 target 값을 비교한다.

class Solution {
    int count = 0;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        dfs(numbers, 0, target, 0);
        answer = this.count;
        
        return answer;
    }
    public void dfs(int[] numbers, int depth, int target, int result){
        // 트리 끝이라면 target과 비교
        if(depth == numbers.length){ 
            if(result == target) this.count++;
            return;
        }
        // 덧셈과 뺄셈 각각 계산
        dfs(numbers, depth+1, target, result + numbers[depth]);
        dfs(numbers, depth+1, target, result - numbers[depth]);
    }
}

 

동적계획법(다이나믹)을 이용한 풀이

마지막 return문에서 dfs를 한 번 더 호출해서 분기를 만들어준다.

n이 numbers.length에 도달할 때 까지 다음 숫자가 음수인 경우와 양수인 dfs를 반복..

모든 경우의 수를 빠르게 찾을 수 있음..

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);
    }
}

 

 

BFS를 이용한 풀이

numbers에 있는 숫자를 더하거나 뺀 경우를 수평적으로 추가

stack에 모든 계산 결과가 담기게 되고 이후 target값과 비교해서 결과 출력

import java.util.ArrayList;
import java.util.Stack;
class Solution {
	public int solution(int[] numbers, int target) {
		int answer = 0;
		int stackNum = 0;
		int	nextNum = 0;
		
		ArrayList<Integer> list;
		Stack<Integer> stack = new Stack<Integer>();
		
		stack.push(numbers[0]);
		stack.push(numbers[0]*-1);
		
		for (int i = 1; i < numbers.length; i++) {
			nextNum = numbers[i];
			list = new ArrayList<Integer>();
				
			while(!stack.isEmpty()) {
				stackNum = stack.pop();
					
				list.add(stackNum+nextNum);
				list.add(stackNum+(nextNum*-1));
			}
				
			for (int j = 0; j < list.size(); j++) {
				stack.push(list.get(j));
			}
		} 
	    	
	    for (Integer sum : stack) {
	    	if(sum == target)
	    		answer++;
		}
	    return answer;
	}
}