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

문제설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 

방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 

return 하도록 solution 함수를 작성해주세요.

 

제한사항

주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

풀이 접근

전형적인 DFS알고리즘 문제이다 하나를 선택하느냐 아니면 선택하지 않고 그 다음 인덱스를 선택하거나의 유형을 가진 문제이다. 본인의 경험상 코딩 테스트나 회사 면접용 문제로 하나로 DFS/BFS는 한 문제씩은 나왔던 걸로 기억한다. 주말에 시간내서 DFS/BFS 설명 및 문제 접근에 대해 설명하는 포스트를 쓰기로... 기약해보자...  문제 접근은 크게 어렵지 않다. 하나의 깊이를 끝까지 파고 들어가는 방식이 DFS다 차이점은 앞서 말했듯 다음 포스트에... 여튼 이 문제는 배열안에 담긴 숫자들을 모두 사용하여야 하기에 선택 안하는 판단은 없다 대신 선택했을때 그 배열안 데이터가 양수인지 음수인지를 판별하는 방식이기 때문에 인덱스를 담당하는 flag변수는 계속 증가하게 만들고 최종 계산을 위한 SUM값은 해당 인덱스의 데이터의 총합을 담당하게 둔다. 말로하면 어렵다. 나도 그랬다 많이 하다보니 그냥 감으로 풀기 시작하는 안좋은 상황까지 오고야 마는데  천천히 재귀 호출을 써보며 따라해가는 걸 추천한다.. 

public class Solution {
	static int total_Len;
	static int targetNum;
    static int count;
    
    public static int solution(int[] numbers, int target) {

    	total_Len = numbers.length;

        targetNum = target;
        count = 0;



        DFS(0,0,numbers);
        int answer = count;
        return answer;
    }
    public static void DFS(int flag,int sum,int[] compNum){
        if(flag==total_Len){
            if(targetNum==sum){
                count++;
                return;
            }else{
                return;
            }
        }

            int tmpNum = compNum[flag];
            DFS(flag+1,sum+tmpNum,compNum);
            DFS(flag+1,sum-tmpNum,compNum);


    }
}