프로그래머스 타겟 넘버 Swift

풀이

numbers의 값을 저장할 변수를 만들어줍니다. -> var numbersCopy = [Int]()

target 값을 저장할 변수를 만들어줍니다. -> var targetCopy = 0

방법의 수를 저장할 변수를 만들어줍니다. -> var count = 0

 

numbers의 숫자들을 차례로 더하거나 뺏을 때 두가지 모두를 실행시키도록 하여 깊이가(depth) numbers의 갯수에 도달하면 반환하도록 하는 재귀함수를 만들어줍니다.(dfs)  func dfs(_ depth: Int, _ sum: Int) { if depth == numbersCopy.count { ... }  return }

numbers의 갯수에 도달했을 때 합이 target의 값과 같다면 방법의 수를 증가시켜주도록해줍니다. =>  if sum == targetCopy {  count += 1 } 

합에 다음 숫자를 더해줄 dfs와 합에 다음 숫자를 뺄 dfs를 각각 재귀하도록 해줍니다.

=>   dfs(depth + 1, sum + numbersCopy[depth])

       dfs(depth + 1, sum - numbersCopy[depth])

초기값으로 dfs에 (0,0)을 넣어주고 numbers가 [1,1,1,1,1]이고 taget이 3인 함수를 실행시키면

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

    

    numbersCopy = numbers

    targetCopy = target

    dfs(0, 0)

 

    return count

}

 

depth = 1

1

-1

depth = 2

2 0 

0 -2

depth = 3

3 1  1 -1

1 -1 -1 -3

depth = 4

4 2 2 0 2 0 0 -2

2 0 0 -2 0 -2  -2 -4

depth = 5

5 3  3 1  3 1  1 -1 3 1  1 -1  1 -1  -1 -3 

3 1  1 -1  1 -1  -1 -3  1 -1 -1 -3  -1 -3 -3 -5

3인 숫자가 총 5개 이므로 정답은 5가 됩니다.

 

이번 문제는 재귀함수를 이용하는 DFS(Depth - First - Search) 깊이우선탐색으로 풀었어야 하는 문제였는데

DFS를 모르고 있어서 정말 복잡하게 생각하다가 결국 구글링해서 DFS문제인것을 알고 풀게 되었다.

 

전체 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

var numbersCopy = [Int]() var targetCopy = 0 var count = 0   func dfs(_ depth: Int, _ sum: Int) {       if depth == numbersCopy.count {         if sum == targetCopy {             count += 1         }         return     }          dfs(depth + 1, sum + numbersCopy[depth])     dfs(depth + 1, sum - numbersCopy[depth])      }   func solution(_ numbers:[Int], _ target:Int) -> Int {          numbersCopy = numbers     targetCopy = target     dfs(0, 0)          return count } Colored by Color Scripter