[알고리즘] 프로그래머스 타겟 넘버 -깊이/너비 우선 탐색(DFS/BFS)-

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

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

 

프로그래머스 LEVEL2 의 타겟넘버를 풀어봤습니다. ㅎㅎ

+ 일떄와 - 일때 두가지 경우로 재귀를 돌려 결과값이  타겟넘버라면 개수를 1 증가시키게 풀었습니다.

 

문제풀이는 다음과 같습니다.

 

[Java]

class Solution {
    private static int target;
    private static int size;
    private static int answer = 0;
    private static int[] numbers;

    public static void dfs(int n, int count) {
        if (count == size-1) {
            if (n == target) {
                answer++;
            }
        } else {
            dfs(n + numbers[count+1], count + 1);
            dfs(n + (numbers[count+1]*-1), count + 1);
        }
    }

    public int solution(int[] numbers, int target) {
        size = numbers.length; //5
        Solution.target = target; //3
        Solution.numbers = numbers;
        dfs(numbers[0], 0); // 1
        dfs(numbers[0]*-1, 0); // -1
        return answer;
    }
}

 

[Kotlin]

    internal class Solution {

        fun solution(numbers: IntArray, target: Int): Int {
            size = numbers.size //5
            Solution.target = target //3
            Solution.numbers = numbers
            dfs(numbers[0], 0) // 1
            dfs(numbers[0] * -1, 0) // -1
            return answer
        }

        companion object {
            private var target: Int = 0
            private var size: Int = 0
            private var answer = 0
            private var numbers: IntArray? = null

            fun dfs(n: Int, count: Int) {
                if (count == size - 1) {
                    if (n == target) {
                        answer++
                    }
                } else {
                    dfs(n + numbers!![count + 1], count + 1)
                    dfs(n + numbers!![count + 1] * -1, count + 1)
                }
            }
        }
    }