[programmers] 타켓넘버 with 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 이하인 자연수입니다.

 

풀이

모든 경우의 수를 구하는 방법이 최선이라고 생각했다.

solution 인스턴스에서, numbers array의 첫번째 인덱스 값이 +인경우와 -인 경우를 모두 구하는 방향으로 진행하였고,

이후 dfs 인스턴스에서도 동일하게 진행한다.

 

다만, dfs 인스턴스에서는 index 비교를 통해 해당 로직이 모두 완료되었는지 확인해보고,

target으로 주어진 값과, numbers를 각각 +, - 로 연산하여 얻은 결과가 동일하다면

return 값을 1로 주고 answer에 1을 추가할 수 있도록 진행한다. 

class Solution {
    public int dfs(int[] numbers, int target, int prev_num, int index){
        if (index == numbers.length){
            if (target == prev_num){
                return 1;
            }
            else {
                return 0;
            }
        }

        int answer = dfs(numbers, target, prev_num + numbers[index], index+1) + dfs(numbers, target, prev_num - numbers[index], index+1);

        return answer;
    }

    public int solution(int[] numbers, int target) {
        int answer = dfs(numbers, target, numbers[0], 1) + dfs(numbers, target, -numbers[0], 1);

        return answer;
    }
}

 

아쉬웠던 점

오랜만에 알고리즘 문제를 풀었더니, 또 자바 언어에 능숙하지 못한 상태라 손에 익숙하지 않았다.

오랜만에 마주친 dfs 는 아직도 어색하고 이해가 잘 되진 않았으나,

매일 조금씩 하다보면 나아지겠지 하고 생각하는 중..

 

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

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