[Swift 알고리즘] 타겟 넘버 - 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=swift

---

접근 방법

모든 경우의 수를 따지려면 DFS가 적합하겠다.
시간 복잡도는 O(2^N)이지만, 2 ** 20 ≈ 1,000,000이므로 가능하다.

방향이 두 가지(+, -)가 있는 그래프를 탐색한다고 생각하면 쉽다.
dfs 함수가 재귀적으로 + / - 의 경우를 각각 호출하고,
깊이가 numbers와 같아지면, target과 비교하여 cnt하는 방식으로 풀어보자.

의사 코드

func dfs(depth:int, sum:Int) -> Int
     depth == numbers.size && sum == target인 경우 cnt += 1
     depth + 1이 범위(numbers.size) // 벗어나면 return
     // 두 가지 방향 재귀적으로 탐색
     dfs(depth + 1, sum + numbers[depth + 1])
     dfs(depth + 1, sum - numbers[depth + 1])

 func solution()
 dfs(-1, 0) 호출
 return cnt

나의 풀이

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {

    func dfs(_ depth: Int, _ sum: Int) {
        if depth == numbers.count - 1 && sum == target {
            cnt += 1
            return // 재귀 탐색 종료
        }

        // depth + 1이 범위(numbers.count)보다 작으면 진행, 벗어나면 return
        guard depth + 1 < numbers.count else { return }

        // 두 가지 방향 재귀적으로 탐색
        dfs(depth + 1, sum + numbers[depth + 1])
        dfs(depth + 1, sum - numbers[depth + 1])
    }
    
    var cnt = 0
    dfs(-1, 0) // 첫 번째 인덱스부터 방향이 갈리므로

    return cnt
}

 

의사 코드에서는 함수를 분리했지만, cnt 변수를 관리하는 것이 까다로워서 중첩으로 풀이.

특별한 점은 없고, Swift의 경우에는 index가 벗어나는 것을 guard로 관리하면 깔끔하다.

더 나은 풀이

import Foundation

func dfs(_ depth: Int, _ sum: Int, _ numbers: [Int], _ target: Int) -> Int {
    if depth == numbers.count - 1 {
        return sum == target ? 1 : 0
    }
    // 다음 깊이로 재귀 호출하고, 각 경우의 수를 더함
    return dfs(depth + 1, sum + numbers[depth + 1], numbers, target) +
           dfs(depth + 1, sum - numbers[depth + 1], numbers, target)
}

func solution(_ numbers: [Int], _ target: Int) -> Int {
    return dfs(-1, 0, numbers, target)
}

 

이 풀이가 압도적으로 깔끔하고, 관리하기도 좋다.

SOLID의 단일 책임 원칙(SRP)을 잘 지키고 있다.

또한 다른 함수의 변수에 접근하려면, 현재 함수의 매개변수로 넘겨줘야 한다는 것을 기억하자.

 

주목할 부분은 경우의 수를 세는 cnt 변수를 따로 관리하고 있지 않다는 점이다.

위 코드에서는 재귀 함수가 두 가지 경우의 반환값의 합을 return 하고 있다.

이렇게 하면 별도 변수 없이도 stack에 반환값을 관리할 수 있다.

이것을 반드시 기억하자.