Algorithm)Programmers- 타겟 넘버 swift

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

프로그래머스

 

주어지는 숫자 개수가 2개 이상 20개 이하이고, case를 거듭할 때마다 +, - 두 케이스씩 늘어나므로 완전탐색 or bfs, dfs라 생각했습니다 

 

처음에는 아래와 같이 작성했는데 테스트1, 2 에서 시간 초과가 떴습니다

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var q = [Int]()
    q.append(numbers[0])
    q.append(-numbers[0])
    for i in 1...numbers.count - 1 {
        for _ in 0...q.count-1 {
            let tmp = q.removeFirst()
            q.append(tmp + numbers[i])
            q.append(tmp - numbers[i])
        }
    }
    
    var cnt = 0
    for i in q {
        if i == target {
            cnt += 1
        }
    }
    
    return cnt
}

var a = [1, 1, 1, 1, 1]
var b = 3
var sol = solution(a, b)

이후에 서칭을 통해 DFS 풀이를 보고 적용해봤더니 통과했습니다

import Foundation

var numbers = [Int]()
var target = 0
var cnt = 0

func dfs(_ depth: Int, _ sum: Int) {
    if depth == numbers.count {
        if sum == target {
            cnt += 1
        }
        return
    }
    dfs(depth + 1 ,sum + numbers[depth])
    dfs(depth + 1 ,sum - numbers[depth])
}

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

로직은 비슷한데 왜 첫 코드는 시간초과가 떴을까,,, 생각해보니 removeFirst는 사용 여부가 시간초과 나고 안나고를 결정하지 않았을까 생각됩니다