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

programmers.co.kr/learn/courses/30/lessons/43165

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

문제 요약

 int 배열인 numbers의 값들을 하나씩 더하거나 빼서 target으로 만들 수 있는 경우의 수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 저번 코테에서 탐색에 약하다는 사실을 깨닫고 풀어본 첫번째 탐색 문제이다. 레벨 2 문제가 맞나 싶을 정도로 난이도가 낮은 문제인 것 같다. DFS를 이용해서 배열의 인덱스를 하나 씩 재귀로 더하거나 뺐다. 그리고 depth가 numbers 배열의 길이와 같아졌을 때 그 수를 target과 비교하면 된다.

 

 처음에 풀었을 때는 answer을 전역변수로 놓고 풀었으나 전역변수의 사용을 자제하고자 answer을 ++하는 것보다 함수를 return하는 방식으로 바꾸었다. if 문안에 if문 대신 삼항연산자를 사용하여 라인을 조금 더 줄여나갔다.

 

나의 코드

public class 타겟_넘버 {
    public int solution(int[] numbers, int target) {
        return findTarget(numbers, target, 0, 0);
    }

    public int findTarget(int[] numbers, int target, int depth, int result) {
        if (depth == numbers.length)
            return (result == target) ? 1 : 0;

        return findTarget(numbers, target, depth + 1, result + numbers[depth])
                + findTarget(numbers, target, depth + 1, result - numbers[depth]);
    }
}