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

난이도 : Lv 2

분류 : 깊이/너비 우선 탐색(DFS/ BFS)

 

문제

 

프로그래머스

 

코드

 

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var count = 0
    
    func DFS(_ index: Int, _ sum: Int) {
    
        if index == (numbers.count - 1) && sum == target {
        // 재귀함수 탈출 조건
        
            count += 1
            return
        }
        guard index + 1 < numbers.count else { return }
        
        DFS(index+1, sum + numbers[index + 1])
        // 덧셈 연산 수행한다.
        
        DFS(index+1, sum - numbers[index + 1])
        // 뺄셈 연산을 수행한다.
    }
    
    DFS(-1, 0)
    // DFS(0, 0) 으로 시작한다면 numbers 의 0번째 인덱스는 사용하지 않게된다.
    
    return count
}

 

풀이

1. 인자로 인덱스와 합계를 받는 DFS 함수를 정의한다.

2. 더하고 빼서 타겟 넘버를 구해야 하기 때문에 덧셈 연산과 뺄셈 연산을 수행하게 구현한다.

 

P.S

재귀함수에 대한 이해가 없다면 상당히 곤란한 문제입니다. 곧 재귀함수에 관한 글을 포스팅 하겠습니다.