[Swift 알고리즘] 프로그래머스(Lv.2) - 타겟 넘버

안녕하세요. 개발 중인 정주입니다.

 

오늘은 프로그래머스(Lv.2) - 타겟 넘버 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 타겟 넘버

 

---

풀이

이번 문제는 깊이 우선 탐색(DFS) 문제입니다.

 

예제 2를 예시로 들겠습니다. 예제 2를 그래프로 그리면 아래처럼 나오는데요.

1. 0 -> +4 -> +1 -> +2 -> +1 

2. 0 -> +4 -> +1 -> +2 -> -1

3. 0 -> +4 -> +1 -> -2 -> +1 

4. 0 -> +4 -> +1 -> -2 -> -1 

...

처럼 한 번에 leaf까지 탐색하고 돌아와서 다시 leaf까지 가는 방식입니다.

 

dfs는 재귀를 이용하면 슈도코드와 유사하게 구현이 가능합니다.

시작은 index 0, sum 0이며 index는 1씩 증가시키고 sum은 +number[index]와 -number[index]를 합해서 전달합니다.

depth가 numbers의 depth와 동일해지면 sum을 확인하여 동일하다면 count를 증가시킵니다.

 

---

전체 코드

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var count = 0
    
    func dfs(index: Int, sum: Int) {
        if index == numbers.count {
            if sum == target {
                count += 1
            }
            
            return
        }
        
        dfs(index: index+1, sum: sum + numbers[index])
        dfs(index: index+1, sum: sum - numbers[index])
    }
    
    dfs(index: 0, sum: 0)
    
    return count
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.