[프로그래머스 | JAVA ] LV. 2 : 타겟 넘버

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] :   LEVEL 2 

프로그래머스 타겟 넘버

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

프로그래머스

 

---

● 풀이 방법

해당 문제는 dfs를 사용하여 간단하게 풀어 나갈 수 있다.

재귀함수를 통해서 현재까지 계산된 결과 값, 그 다음으로 계산할 숫자에 대해서 더한 결과값과 뺸 결과값을 각각 재귀함수를 통해 호출한다.

즉 현재 인덱스에서 다음 인덱스의 계산을 진행하게 될때, 해당 인덱스의 숫자에 관하여 더하기 및 빼기의 계산 총 2회가 필요하므로 트리형식의 재귀함수 호출이 진행 될 것이다.

마지막 인덱스의 계산을 마쳤을 때 targer의 결과값과 일치하는지를 확인 한 후, 일치할 경우 1을 리턴, 그렇지 않을 경우 0을 리턴하여 총 targer의 숫자를 만들기위해 사용될 수 있는 방법의 개수를 구할 수 있다.

---

● 소스 코드

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    public int dfs(int[] numbers, int target, int sum, int idx){
        //탈출 조건
        if(idx == numbers.length)
            return sum == target ? 1 : 0;
        
        //재귀 호출
        return dfs(numbers, target, sum + numbers[idx], idx + 1) +
            dfs(numbers, target , sum - numbers[idx], idx + 1);
    }
}

 

매개변수로 건내받은 String 데이터 타입의 s에서 문장을 Split을 통해 잘라낼 수 있으나,

리턴값이 String 이기에 따로 Split으로 자르지 않고 ' '를 기반으로 단어의 시작점을 잡았다.

우선 전체 단어들을 모두 소문자로 변환 시켰고, String s의 첫번째 글자와 ' '이후의 다음 글자를 대문자로 변환 시켰다.

---

● 결과