프로그래머스 - 타겟 넘버

처음에 모든 수를 한 번씩 다 써봐야 한다는 것 외에, 예시 때문에 사용하는 순서도 상관이 있는 줄 착각했다. 그래서 도저히 모르겠어서 다른 풀이를 한참 보고 나서 이해했다. (알고보니 순서는 상관이 없었다.)

우선 모든 수를 한 번씩 다 써봐야 한다.
그래서 나는 자연스럽게 백트래킹으로 완전탐색을 하려고 했는데 다른 사람들 블로그를 보면 백트래킹을 사용하니 시간초과가 나온다는 것이었다.
그래서 BFS를 사용한다고 했는데, 나는 완전탐색에 BFS도 사용한다는 것과 그 예시를 처음 알았다.

풀이
1. 먼저 numbers의 첫번째 수를 양수와 음수로 각각 큐에 넣는다.
2. 큐에서 수를 하나 꺼내고, 그 다음 numbers 수를 양수와 음수로 각각 더해서 다시 큐에 넣는다.
3. 큐에서 수를 하나 꺼냈는데 numbers의 마지막 수까지 더한 값이면 pop하고, 만약 그 수가 taget과 같다면 answer++한다.
4. queue.isEmpty()까지 반복한다.

import java.util.*;
class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        //아 순서는 상관없구나
        //그럼 다 한 번씩 만 써서 
        //0. 하나를 꺼낸다.
        //1. 0에다가 -numbers[i], +numbers[i]를 넣는다
        //2. numbers[length-1]까지 더한 경우, taget이면 answer++ 후 pop
        Stack<Pair> queue = new Stack<>();
        queue.add(new Pair(numbers[0], 1));
        queue.add(new Pair(numbers[0]*-1, 1));
        while(!queue.isEmpty()){
            Pair nowPair = queue.pop();
            if(nowPair.useN == numbers.length){
                if(nowPair.n == target){
                    answer++;
                }
                continue;
            }
            queue.push(new Pair(nowPair.n + numbers[nowPair.useN], nowPair.useN+1));
            queue.push(new Pair(nowPair.n - numbers[nowPair.useN], nowPair.useN+1));
        }
        return answer;
    }
    static class Pair{
        int n;	//지금까지 더한 수
        int useN;	//numbers의 몇 번째 원소까지 더한 수인지
        Pair(int n, int useN){
            this.n = n;
            this.useN = useN;
        }
    }
}

당연히 BFS를 쓰든, DFS를 쓰든 똑같다.(Queue던 Stack이던 상관 X)