[programmers/Swift] 타겟 넘버

programmers.co.kr - 코딩테스트연습 - Lv.2 - DFS/BFS - 타겟 넘버

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

Constraints :

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

 

Solution.swift :

//
//  Created by Yongwoo Marco on 2022/05/09.
//  Copyright © 2022 Yongwoo Marco Kim. All rights reserved.
//

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var count = 0
    
    func searchByDFS(depth: Int, value: Int) {
        guard depth != numbers.count else {
            if target == value {
                count += 1
            }
            return
        }
        searchByDFS(depth: depth + 1, value: value + numbers[depth])
        searchByDFS(depth: depth + 1, value: value - numbers[depth])
    }
    
    searchByDFS(depth: 0, value: 0)
    
    return count
}

print(solution([1, 1, 1, 1, 1], 3)) // 5
print(solution([4, 1, 2, 1], 4)) // 2

How I tried this :
주어진 배열을 모두 연산해야하고 + 또는 - 두가지만 구별하면 되기 때문에

DFS 형태로 모든 배열 요소의 연산이 끝날때까지 타고 들어가도록 구현

depth 즉 배열요소의 인덱스가 끝까지 도달하면 함수를 마치고, 타겟과 같은지 비교해서 같으면 경우의 수를 하나 추가

문제에 관한 모든 저작권 : https://programmers.co.kr/