타겟 넘버

[문제 접근법]

- 해당 숫자들로 Target 숫자를 만들 수 있는지 모든 경우의 수를 구하여 그 값을 리턴하면 된다.

아래의 그림 1의 예시로  모든 경우의 수를 구해보자(아래 표 참고)

 

그림 1 - 문제 설명

 

모든 경우의 수

numbers[0]	numbers[1]	numbers[2]	numbers[3]	numbers[4]	총합
+1	+1	+1	+1	+1	5
+1	+1	+1	+1	-1	3
+1	+1	+1	-1	+1	3
+1	+1	+1	-1	-1	1
+1	+1	-1	+1	+1	3
+1	+1	-1	+1	-1	1
+1	+1	-1	-1	+1	1
+1	+1	-1	-1	-1	-1
+1	-1	+1	+1	+1	3
+1	-1	+1	+1	-1	-1
...	...	...	..	..	..

 

위의 표처럼 모든 경우의 수를 구하여 총합이 target과 같은 개수를 반환하면 된다.

 

총 3가지의 방법으로 완전 탐색을 하여 문제를 풀어보았음. 아래의 코드를 보면서 좀 더 쉽게 이해해보자.

 

 

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

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

 

---

[구현 1] 

-  재귀를 활용하여 모든 경우의 수 탐색한다.  

  

public class TargetNumber {

	static int counts =0;

    //DFS 탐색(Recursion)
    public void getTargetNumberRecursion(int[] numbers, int target, int sum, int idx){
        if(sum == target && numbers.length == idx)  //해당값이 같고 모든 수를 다 활용헀으면
            counts++;

        if(numbers.length == idx)    //반복문 끝이면 종료
            return;

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

	public int solution(int[] numbers, int target) {
        getTargetNumberRecursion(numbers,target,0,0);
        return counts;
    }
    
}

 

[구현 2]

- Stack을 활용하여 모든 경우의 수 탐색

public class TargetNumber {

    //DFS 탐색(Stack)
    public int getTargetNumberStack(int[] numbers,int target){
        int count=0;

        Stack<Integer []> stack=new Stack<>();
        stack.push(new Integer[]{0,0});    //값, 인덱스

        while(!stack.isEmpty()){
            Integer[] nums = stack.pop();

            if(nums[0] == target && nums[1] == numbers.length) 
                count++;
        
            if(nums[1] == numbers.length) continue;

            stack.push(new Integer[]{nums[0] + (numbers[nums[1]] * -1), nums[1] + 1});
            stack.push(new Integer[]{nums[0] + numbers[nums[1]], nums[1] + 1});

        }

        return count;
    }

	public int solution(int[] numbers, int target) {
        int answer = getTargetNumberStack(numbers, target);
        return answer;
    }
    
}

 

[구현 3]

- 큐를 이용하여 모든 경우의 수 탐색

public class TargetNumber {

	//BFS 탐색(Que)
    public int getTargetNumberQue(int[] numbers,int target){
        int count=0;

        Queue<Integer []> que =new LinkedList<>();
        que.add(new Integer[]{0,0});    //값, 인덱스

        while(!que.isEmpty()){
            Integer[] nums = que.poll();

            if(nums[0] == target && nums[1] == numbers.length) 
                count++;
                
            if(nums[1] == numbers.length) continue;

            que.offer(new Integer[]{nums[0] + (numbers[nums[1]] * -1), nums[1] + 1});
            que.offer(new Integer[]{nums[0] + numbers[nums[1]], nums[1] + 1});

        }

        return count;
    }



    public int solution(int[] numbers, int target) {
        int answer = getTargetNumberQue(numbers, target);
        return answer;

    }
    
}