[Programmers] 타겟 넘버

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

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

타겟 넘버

DFS로 푸는 것 까지는 이해를 했는데, 역시나 코드에서 막힌다.

배열에서 요소 하나를 꺼내서 작업할때마다 더하거나, 빼거나 두개의 경우의 수가 생기고

depth는 배열의 length만큼 진행되는 탐색방법을 사용해야겠다고 생각했다.

 

가장 깊은 마지막 depth에서 즉, number.length = 1일 때 이 값이 target이라면 1을 더하고 아니라면 0을 더한다.

이 이후로 머릿속에서 로직이 꼬였다.

답변 봤더니 답안만 머리에 남고..DFS는 적용하는 연습이 아주 많이 필요하다.

---

풀이 - 미완

public class TargetNumber0406 {
    public static int solution(int[] numbers, int target) {
        int answer = 0;
        int size = numbers.length;

        // number의 가장 마지막 요소가 target과 같으면 인데
        // 재귀함수를 쓰면 index 값을 어떻게 처리해야할 지 고민
        if(size == 1){
            if (numbers[] == target){
                return 1;
            }else{
                return 0;
            }
        }

        // while을 쓴다면 조건을 어떻게 걸어야 할 지
        // - 와 + 두 경우가 계속 반복
        // solution(numbers, target-numbers[i])
        // solution(numbers, target+numbers[i])

        return answer;
    }

}

 

 

자바, 파이썬 정답 풀이 >>>

자바 풀이

class Solution {
    public static int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    public static int dfs(int [] numbers, int target, int sum, int idx){
        if (idx == numbers.length){
            return target == sum ? 1 : 0;
        }else{
            return dfs(numbers, target, sum + numbers[idx], idx + 1)
                    + dfs(numbers, target, sum - numbers[idx], idx + 1);
        }
    }
}

 

파이썬 풀이

def solution(numbers, target):
    return dfs(numbers, target, 0, 0)


def dfs(numbers, target, total, i):
    if i != len(numbers):
        return dfs(numbers, target, total + numbers[i], i + 1)\
               + dfs(numbers, target, total - numbers[i], i + 1)
    else:
        return 1 if target == total else 0