프로그래머스 Lv.2: 타겟 넘버 - Swift 풀이

오랜만에 Swift 풀이입니다.

문제 설명

프로그래머스

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

• 1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4 +4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

풀이 과정

모든 경우의 수를 확인하는 방법밖에 없을 것 같은데, 마침 숫자 개수도 최대 20개입니다.

하나의 숫자로 할 수 있는 건 + (더하기) / - (빼기) 2가지입니다. DFS(재귀) 방식으로 탐색한다면 숫자가 n개일 때 최악의 시간 복잡도는 O(2^n)이 됩니다. 2^20 = 1,048,576 으로 백만대라서 괜찮네요.

배열을 인덱스 기준으로 한칸씩 옮겨가며 해당 인덱스의 숫자를 더하는 경우와 빼는 경우를 각각 재귀로 탐색해서 해결합니다. 재귀의 종료 조건은 인덱스가 배열의 끝까지 도달했을 때가 됩니다.

정답 코드

import Foundation

func solution(_ numbers: [Int], _ target: Int) -> Int {
    var answer: Int = 0
    
    func DFS(_ index: Int, _ sum: Int) {
        // 인덱스가 배열의 길이만큼일 때 -> 재귀 또 들어가면 인덱스 넘으니까 여기서 종료 
        if index == numbers.count {
            // 총합이 타겟 넘버와 같으면 카운트 증가
            if target == sum {
                answer += 1
            }
            return
        }
        // 인덱스 하나 키워주고, 현재 인덱스의 숫자를 sum에 더했을 때 재귀로 탐색
        DFS(index + 1, sum + numbers[index])
        // 인덱스 하나 키워주고, 현재 인덱스의 숫자를 sum에서 뺐을 때 재귀로 탐색
        DFS(index + 1, sum - numbers[index])
    }
    
    // 인덱스 0, 총합 0으로 DFS 시작
    DFS(0, 0)
    
    return answer
}

이상입니다.