프로그래머스 - 타겟넘버

타겟넘버

                                         [0](Z)                               // 1    / 2의 0승
                  +1(A)                                   -1(H)               // 2    / 2의 1승
            +1(B)      -1(C)                        +1(I)       -1(J)         // 4    / 2의 2승
          +1(D)  -1(E)  +1(F)   -1(G)         +1(K)  -1(L)   +1(M)  -1(N)     // 8    / 2의 3승

해당 문제를 해결하는데 재귀방식이 아닌 Stack을 이용한 DFS방식으로 해결하고 싶었다. 예제를 열심히 보고선 이제 문제를 적용하려고 하니, 적용을 할 수가 없다
그 이유가 뭐인고 하니,,, 내가 예시로 만들어두었던 DFS방식은 유니크한 값을 가지고 있는 노드에 한해서만 가능하고, 해당 문제는 깊이별로 같은수가 설정 될수가 있으므로(예시가 1,1,1,1,1 이다 하필..) 다른방식을 생각해야 한다.

해당 문제에서 가장 중요한것은, 한 뎁스의 값이 있을때 어떻게 +값과 -값을 분기하여 처리할 것인가 이다.
열심히 머리를 굴린결과( 사실 예전에 파이썬으로 할때 대략 어떻게 해야하는지 알고 있지만 그래도 오래 걸렸다..) 다음과 같은 규칙으로 움직이도록 설계했다.

• 한번의 stack loop는 해당 깊이의 시작과 끝이다.
• 한번의 pop결과는 +1값과 -1의 값에 대한 연산이 필요하다.

해당 문제를 결국 나는 DFS가 아닌 BFS가 되어버렸다....

2가지를 가지고 구현한 나의 방식은 다음과 같다.

    private Stack<Integer> stack = new Stack<>();
    public int solution(int[] numbers, int target) {
        // 최초값 삽입 (stack loop가 수행될수 있도록)
        stack.push(0);
        // 깊이별 loop
        for (int number : numbers) {
            // 임시 stack loop마다 초기화가 이루어져야 한다.
            Stack<Integer> tempStack = new Stack<>();
            while (!stack.empty()) {
                // 현재까지 연산된 stack 값 pop
                int value = stack.pop();
                // +값, -값을 각각 stack push
                tempStack.push(number + value);
                tempStack.push((number * -1) + value);
            }
            // Empty된 stack에 다시 loop할 수 있도록 임시 stack의 값 할당
            stack.addAll(tempStack);
        }
        // 최종깊이의 연산값에 대해 target 숫자와 일치하는 개수를 반환
        return (int) stack.stream().filter(num -> num == target).count();
    }

결과값 ( 총 5개)
[1, -1, 3, 1, -1, -3, 1, -1, 3, 1, 5, 3, 1, -1, 3, 1, -1, -3, 1, -1, -3, -5, -1, -3, 1, -1, 3, 1, -1, -3, 1, -1]