프로그래머스 DFS - 타겟 넘버

문제

문제 설명
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 함수를 작성해주세요.

입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2

키포인트 정리

"순서를 바꾸지 않고 더하거나 빼서 타겟의 숫자와 일치해야 한다"라는 키 포인트를 캐치해내야 합니다.

• 순서를 바꾸지 않는다 = Array를 순회하며 처리
• 더하거나 빼서 = 더하는 경우와, 빼는 경우의 수를 추가한다.
• 일치해야 한다 = 모든 배열을 순회 한 후, target과 모두 합한 값이 같을 경우를 체크한다.

정리를 하게 되면 아래의 두가지 상황이 나눠집니다.

1. 끝까지 순회를 했다면 ⮕ 만약 값이 같을 경우, 결과 +1
2. 순회하지 못했다면 ⮕ 빼거나 더하여 다음 단계로 순회 (아래로 탐색)

풀이

해당 케이스는 끝까지 순회한 케이스에 대해 모든 경우의 수를 체크해야 합니다. 그렇기에 순회를 하지 못했다면 재귀를 통해 깊이 탐색을 이어가도록 합니다.

        fun dfs(numbers: IntArray, target: Int, depth: Int, sum: Int) {
            if (depth == numbers.size) {
                // 마지막 깊이까지 도달 후
                when{
                    // 답이 target과 같을 경우 +1
                    // 아닐 경우, 리턴
                    target == sum -> answer += 1
                    else -> return
                }
            }else{
                // 아직 종착지에 오지 않았다면?
                // 노드 값을 더하고
                dfs(numbers, target, depth + 1, sum+numbers[depth])
                // 노드 값을 뺀다
                dfs(numbers, target, depth + 1, sum-numbers[depth])
            }

최종 코드

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

        fun dfs(numbers: IntArray, target: Int, depth: Int, sum: Int) {
            if (depth == numbers.size) {
                // 마지막 깊이까지 도달 후
                when{
                    // 답이 target과 같을 경우 +1
                    // 아닐 경우, 리턴
                    target == sum -> answer += 1
                    else -> return
                }
            }else{
                // 아직 종착지에 오지 않았다면?
                // 노드 값을 더하고
                dfs(numbers, target, depth + 1, sum+numbers[depth])
                // 노드 값을 뺀다
                dfs(numbers, target, depth + 1, sum-numbers[depth])
            }
        }

    }

Chat GPT의 피드백

이제는 GPT가 우리보다 뛰어나기에.. 때로는 GPT의 피드백을 수용할 필요가 있다. GPT의 풀이방식은 어떨지 물어보았다.

GPT의 풀이법

class Solution {
private var count = 0

fun solution(numbers: IntArray, target: Int): Int {
    dfs(numbers, 0, 0, target)
    return count
}

// depth: 현재 인덱스, sum: 지금까지의 합
private fun dfs(numbers: IntArray, depth: Int, sum: Int, target: Int) {
    if (depth == numbers.size) {
        if (sum == target) count++
        return
    }

    // 현재 숫자 더하기
    dfs(numbers, depth + 1, sum + numbers[depth], target)
    // 현재 숫자 빼기
    dfs(numbers, depth + 1, sum - numbers[depth], target)
}

더하기

만약이지만... [5,8,1,1,1,1,1,1,1,1,1,1,1,1,1,1]일 경우에서 타겟넘버가 5라면?
해당 경우라면 남은 값에 대해 더하거나 빼기 전, 남은 depth의 값과 타겟에 대해 가능성이 있는지 체크하는 로직을 추가하는 것도 좋다고 본다.

        // 남은 숫자 합
        val remainSum = numbers.drop(depth).sum()

        // 도달 불가능한 경우
        if (abs(target - sum) > remainSum) return

결과

사실 백트래킹과 DFS를 혼용해서 써야한다고 생각 했다. 이유는
타겟이 앞으로 남은수를 모두 더하거나 모두 뺐을 때의 경우를 걸러낼 수 있어 최적화가 가능하다고 생각했기 때문이다.

이 문제의 제한사항은 적은 깊이와 작은 타겟이기 때문에 백트래킹이 필요없었으나, 대규모로 필요시 같이 혼용해서 알고리즘을 적용해주면 좋을 것 같다는 생각이 들었다.