[Swift] 프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색 > 타겟 넘버

 

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

 

문제풀이

이진트리와 같이 배열로 주어진 모든 수를 완전 탐색할 수 있도록 하였다. 텍스트로 표현하기에 가시성이 떨어지지만 다음과 같다.

 

• 4
  • 1
    • 2
      • 1
      • -1
    • -2
      • 1
      • -1
  • -1
    • 2
      • 1
      • -1
    • -2
      • 1
      • -1

같은 논리를 가진 코드인데 채점 시 한 개의 케이스에 대하여 시간초과였는데 코드를 수정하니 통과되었다.

블로그 포스팅할 때 실행결과 캡처를 위해 다시 채점해보니 통과되었다. 뭐지

 

 

 

 

코드

 시간초과 코드

import Foundation
func solution(_ numbers:[Int], _ target:Int) -> Int {
    func dfs(dept: Int, result: Int){
        if numbers.count-1 >= dept{
            dfs(dept: dept+1, result: result - numbers[dept])
            dfs(dept: dept+1, result: result + numbers[dept])
        }else{
            if result == target{
                count += 1
            }
        }
    }
    var count = 0
    dfs(dept: 0, result: 0)
    return count
}

 

통과 코드

import Foundation

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

 

차이점이라고는 조건 문의 수정과 return의 유무일텐데 1, 2번 케이스에 대하여 절반 정도의 차이가 난다.