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

문제 요약

숫자가 있는 배열이 주어지고 타겟넘버가 주어진다. 이 상황에서 배열 안의 숫자를 더하거나 빼서 타겟넘버와 일치하는 경우가 있을 텐데 모든 경우의 수에서 타겟넘버와 연산 결과가 일치하는 경우를 리턴해야 한다.

 

해답

func solution(_ numbers:[Int], _ target:Int) -> Int {
	// 횟수를 세기 위한 cnt 변수
    var cnt = 0
    func dfs(index: Int, sum:Int) {
        if index == (numbers.count - 1) && sum == target {
            // 현재 +나 - 연산이 모두 끝나고 결과값이 target과 일치할 경우에만 cnt 증가
            cnt += 1
            // return으로 탈출
            return
        }
		// index 에러가 발생하는 것을 막기 위해 필요한 guard문. if로 작성해도 무관
        guard index + 1 < numbers.count else { return }
        // 핵심인 부분으로 재귀로 +과 - 연산을 거듭한다. 위에서 탈출하면 자동으로 아래의 빼는
        // 연산을 마주치기 때문에 모든 연산이 수행 가능하다.
        dfs(index: index+1, sum: sum + numbers[index + 1])
        dfs(index: index+1, sum: sum - numbers[index + 1])
    }
    //dfs를 호출하여 사용. 이 때, index를 0으로 시작하면 재귀로 호출할때 0인 케이스를 못 다루게 된다.
    dfs(index: -1, sum: 0)
    return cnt
}

 

전형적인 DFS 문제이다. 해당 문제를 풀기 위해서 유튜브를 여러번 뒤지고 문제의 해결법을 찾았는데 학습에 시간이 너무 오래 걸린 것 같다.

문제를 풀기 위해서는 DFS, 깊이우선탐색의 개념을 필수적으로 알아야 한다. 기본 원리는 스택이라고 볼 수 있다. 하나의 경우를 모두 탐색하고 나와서 다시 다음 선택지로 넘어가서 탐색을 진행한다. 이번 문제의 경우에는 상대적으로 간단한 구조를 가지고 있어 참고용으로 좋은 것 같다.