타겟 넘버

문제 설명

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 이하인 자연수입니다.

---

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

---

풀이

깊이 우선 탐색과 너비 우선 탐색, 완전 탐색 알고리즘은 내가 유독 어려워한다. 이해하는데 오랜 시간이 걸리는 것도 있거니와 써 버릇하지 않기 때문에 어색한 것도 있다.
다시 문제로 돌아가서 이 문제는 깊이 우선 탐색(DFS)으로 풀면 간단하게 풀 수 있다.
보통 완전 탐색 알고리즘은 재귀 형식으로 구현되는데 맞는 조건을 주고 선택지를 준다고 생각하면 편하다

깊이우선탐색

이진트리 형식으로 그려보면 위와 같이 나온다. 이를 기반으로 구현해보자.

첫째 '맞는 조건'을 만들어줄 필요가 있다.
맞는 조건은 return 하는 조건으로 깊이가 배열의 크기와 같을 때(이진트리의 리프 노드에 도달했을 때)로 볼 수 있다. 이걸 코드로 구현하면 된다

fun dfs(numbers: IntArray, target: Int, depth: Int, num : Int): Int {
    return if (depth == numbers.size) {
        when (num) {
            target -> 1
            else -> 0
        }
    }
      ...
}

when(num)에서 target과 같으면 1을 리턴하고, 다르면 0을 리턴한다.

둘째 재귀 방법을 제시해줘야 한다.
위에서도 언급한 듯이 선택지를 줘야 한다. 우리가 줄 선택지는 두 가지

• 더한 뒤 target에 도달하는 경우
• 빼고 난 뒤 target에 도달하는 경우

코드 한 줄로 만들 수 있다.

    else
        return dfs(numbers, target, depth+1, num+numbers[depth]) + dfs(numbers, target, depth+1, num-numbers[depth])
}

재귀는 처음 보면 정말 안 익숙하다. 일단 재귀의 기본 조건은 depth가 깊어져야 하는 것이다. num은 companion object {}로 구현해도 되지만 그렇게 할 경우 depth가 얕아질 때 num을 원상복구 해줘야 하므로 패러미터로 구현했다.
이렇게 구현할 경우 다음과 같이 된다.

depth : 0 시작
depth : 1 시작 -> 1번
depth : 2 시작 -> 1번 -> 1번
depth : 3 시작 -> 1번 -> 1번 -> 1번
depth : 4 시작 -> 1번 -> 1번 -> 1번 -> 1번
depth : 5 시작 -> 1번 -> 1번 -> 1번 -> 1번 -> 1번
depth : 4 시작 -> 1번 -> 1번 -> 1번 -> 1번
depth : 5 시작 -> 1번 -> 1번 -> 1번 -> 1번 -> 2번
depth : 4 시작 -> 1번 -> 1번 -> 1번 -> 2번
depth : 5 시작 -> 1번 -> 1번 -> 1번 -> 2번 -> 1번
depth : 4 시작 -> 1번 -> 1번 -> 1번 -> 2번
depth : 5 시작 -> 1번 -> 1번 -> 1번 -> 2번 -> 2번
depth : 4 시작 -> 1번 -> 1번 -> 1번 -> 2번
depth : 3 시작 -> 1번 -> 1번 -> 2번
depth : 4 시작 -> 1번 -> 1번 -> 2번 -> 1번

쭉 탐색해 나가면서 맞는 조건에 따라 0 또는 1을 반환한다.
재귀가 내 기준에선 많이 어렵지만 계속 풀다 보면 익숙해질 거 같다. 마지막으로 코드 전문과 자바로 짠 코드를 올리면서 마무리하겠다.

kotlin

class Solution{
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
        answer = dfs(numbers, target, 0, 0)
        return answer
    }

    fun dfs(numbers: IntArray, target: Int, depth: Int, num : Int): Int{
        return if(depth == numbers.size){
            when(num){
                target -> 1
                else -> 0
            }
        }
        else
            return dfs(numbers, target, depth+1, num+numbers[depth]) + dfs(numbers, target, depth+1, num-numbers[depth])
    }
}

머리가 띵해지는 람다 코드

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        return numbers.fold(listOf(0)) { list, i ->
            list.run {
                map { it + i } + map { it - i }
            } 
        }.count { it == target }
    }
}

java

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

    public int dfs(int[] numbers, int target, int depth, int num){
        if(depth == numbers.length){
            if(num == target)
                return 1;
            return 0;
        }
        else
            return dfs(numbers, target, depth+1, num+numbers[depth]) + dfs(numbers, target, depth+1, num-numbers[depth]);
    }
}