프로그래머스] 타겟넘버

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

프로그래머스

풀이

+, - 로 이루어진 그래프가 있다고 생각한다.

해당 그래프를 순회하면서 주어진 숫자배열에 값들을 더하거나 빼면서 target 넘버가 나오는지 확인한다.

 

 

import java.util.*;

class Solution {

    static int count=0; //결과를 저장할 변수
    
    static char[] d = {'+','-'}; //반복문을 쓸거면 사용할 배열

    static public int solution(int[] numbers, int target) {

        bfs(numbers,target);

        System.out.println(count);
        return count;
    }

    static void dfs(int[] numbers , int target, int sum, int index)
    {
        //index변수를 그래프의 depth를 나타내는 변수로 봐도 된다.
        
        if(index == numbers.length){ // 그래프의 끝이라면 

            if(sum == target)
            {
                count++;
            }
            return;
        }
        /*
        dfs 내부에 반복문을 쓰는경우 -> dx,di를 따로 사용할경우 
        여기서 굳이 쓰자면 char[]를 이용하면 될듯 */
    
        //2가지 경우이고, +,-연산을 사용하는경우라 반복문없이 하는게 편리
        dfs(numbers,target,sum+numbers[index],index+1);
        dfs(numbers,target,sum-numbers[index],index+1);


    }

    static void bfs(int[] numbers,int target)
    {
        Queue<int[]> q = new LinkedList<>();  //depth, sum
        
        q.add(new int[]{0+1,0+numbers[0]});
        q.add(new int[]{0+1,0-numbers[0]});
    
        while(!q.isEmpty())
        {
            int[] currentNode = q.poll();
            int currentDepth = currentNode[0];
            int currentSum = currentNode[1];
            
            if(currentSum == target && currentDepth == numbers.length)
            {
                count++;
            }
            
            if(currentDepth < numbers.length)
            {
                int nextSum1 = currentSum + numbers[currentDepth];
                int nextSum2 = currentSum - numbers[currentDepth];
                
                int nextDepth = currentDepth + 1 ;
                
                q.add(new int[] {nextDepth,nextSum1});
                q.add(new int[] {nextDepth,nextSum2});
            }
            
            
        }
    }
        

    
}