[프로그래머스/Java] 타겟 넘버

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

프로그래머스

 

DFS문제입니다.

그냥 스택을 이용하여 푸는 방법과, 클래스를 만들어 푸는 방법 2가지로 나누어 진행하였습니다.

먼저 스택을 이용한 방법입니다.

class Solution {
            static Stack<Integer> stack1= new Stack<Integer>();
            static Stack<Integer> stack2= new Stack<Integer>();
            static int[] num;
            static int g;
            static int cnt=0;
            public int solution(int[] numbers, int target) {


                g=target;
                num=numbers;
                stack1.push(0);
                dfs();

                return cnt;
            }

            private void dfs() {
                for(int i=0;i<num.length;i++)
                {
                    while (!stack1.isEmpty()){
                        int n= stack1.pop();
                        stack2.push(n+num[i]);
                        stack2.push(n-num[i]);
                    }
                    stack1=stack2;
                    stack2= new Stack<>();
                }
                while (!stack1.isEmpty()){
                    if(g==stack1.pop())
                        cnt++;
                }
            }
        }

이번에는 클래스를 이용한 풀이입니다.

import java.util.*;
class Solution {
            private static class State{
                int index;
                int result;

                public State(int index, int result) {
                    this.index = index;
                    this.result = result;
                }
            }
            public int solution(int[] numbers, int target) {
                Stack<State> s= new Stack<>();
                s.push(new State(0,0));
                   
                int cnt=0;
                while (!s.isEmpty())
                {
                    State state= s.pop();
                    if(state.index==numbers.length){
                        if(state.result==target)
                        {
                            cnt++;
                        }
                        continue;
                    }
                    //+와-를 선택한 경우를 각각 계산
                    s.push(new State(state.index+1,state.result+numbers[state.index]));
                    s.push(new State(state.index+1,state.result-numbers[state.index]));
                }
                return cnt;
            }
        }

저는 깊이 우선 탐색 문제와 너비 우선 탐색 문제에 아직 덜 익숙해져있어서, 최대한 많이 풀어봐야 할 것 같습니다.

dfs의 문제 해결 과정

1. 방문 검사 배열

2. 초기 상태

3. 탐색진행

4. 중복검사

5. 현재상태처리

6. 전이상태생성

7. 범위&유효성 검사

8. 상태전이

이 문제에서는 서로 다른 경로를 선택하며, 중복이 발생하지 않고. 따라서 1과 4의 과정은 생략할 수 있습니다.

그리고 2차원 배열안에서 범위를 검사하는 문제가 아니므로 And OR연산자를 통한 범위 검사는 하지 않아도 됩니다.

따라서 7번의 과정도 생략하였습니다.