DFS/BFS_Programmgers_타겟 넘버 [swift]

코딩테스트를 보다가.. 너무 못해진 것 같기도하고 그래서 다시 공부를 시작

풀어 본 건 아니지만, 해당 유형이 기억이 안날 줄 알았는데 생각보다 빠르게 품 13분?

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

정답 코드

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var sol = 0
    
    var queue = numbers
    let firstItem = queue.removeFirst()
    
    sol += recursive(startItem: -firstItem, restItem: queue, target: target)
    sol += recursive(startItem: firstItem, restItem: queue, target: target)
    
    return sol
}

func recursive(startItem: Int, restItem: [Int], target: Int) -> Int {
    guard !restItem.isEmpty else { return target == startItem ? 1 : 0}
    
    var currentValue = startItem
    
    var nextQueue = restItem
    let nextItem = nextQueue.removeFirst()
    
    let lhs = recursive(startItem: startItem + nextItem, restItem: nextQueue, target: target)
    let rhs = recursive(startItem: startItem - nextItem, restItem: nextQueue, target: target)
    
    return lhs + rhs
}

 

글을 쓰면서 생각하는데, 문제 조건이 numbers의 순서를 바꾸지 않고, 음수 혹은 양수를 더해서 target이 되는 경우의 수를 구하는 것 이었으므로,

removeLast()를 쓰면 수가 많은 경우에 cow비용이 덜 발생할 것 같다는 생각이 스쳤다.

근데 문제 조건이

 

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

였으므로, 큰 영향은 없었을 것 같음

 

성능

테스트 1 〉	통과 (797.81ms, 16.3MB)
테스트 2 〉	통과 (904.05ms, 16.2MB)
테스트 3 〉	통과 (0.74ms, 16.3MB)
테스트 4 〉	통과 (3.66ms, 16.4MB)
테스트 5 〉	통과 (23.22ms, 16.5MB)
테스트 6 〉	통과 (1.33ms, 16.4MB)
테스트 7 〉	통과 (0.71ms, 16.5MB)
테스트 8 〉	통과 (5.94ms, 16.3MB)