[ 프로그래머스 ] 타겟 넘버

 

🍄 프로그래머스 문제 링크

프로그래머스

✍🏻 문제 풀이 Github 링크

-Swift-CodingTest/프로그래머스/2/43165. 타겟 넘버 at main · BaeJihae/-Swift-CodingTest

 

 

 

문제 설명

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

 

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    
    var answer = 0
    func dfs(now: Int, i: Int){
        if i == numbers.count && now == target {
            answer += 1
        }
            if numbers.count > i {
                dfs(now: now-numbers[i], i: i+1)
                dfs(now: now+numbers[i], i: i+1)
            }
    }
    dfs(now: 0, i: 0)
    return answer
}

 

바로 이전에 피로도를 공부하면서 DFS의 풀이 방법에 대해서 공부하였고, 아침에 해당 문제를 다시 한번 풀어보아서 이번 문제는 복습하는 듯 하였다.

딱 보자마자 재귀함수 DFS로 푸는 것이라고 깨달았고, 피로도와 조금만 바꾼 상태에서 풀었다!

한번만에 풀리는 것을 보고 아주 쾌감이.. 크..

 

 

다른 사람 풀이

import Foundation

func searchTarget(number: [Int], depth: Int, target: Int, value: Int, answer: inout Int) {

    // MARK: - 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
    if depth >= number.count {
        if target == value { answer = answer + 1 }
        return
    }

    // MARK: - 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 
    searchTarget(number: number, depth: depth + 1, target: target, value: value + number[depth], answer: &answer)
    searchTarget(number: number, depth: depth + 1, target: target, value: value - number[depth], answer: &answer)
}

func solution(_ numbers:[Int], _ target:Int) -> Int {

    var answer = 0
    searchTarget(number: numbers, depth: 0, target: target, value: 0, answer: &answer)

    return answer
}

dfs 함수를 따로 만들어서 함수의 매개변수에 depth와 value 뿐만 아니라 추가해야될게 많아진 듯 하다!

나도 dfs 함수를 따로 만드는 연습을 해봐야겠다.

그리고 answer은 값형식을 사용하여 answer 값을 출력하는 return 형태가 아닌 inout 키워드를 써서 함수를 만들었다.

오늘도 또 하나 배운다.

 

 

import Foundation

func caculation(numbers: [Int], target: Int, index: Int, sum: Int) -> Int {
    if index == numbers.count {
        return sum == target ? 1 : 0
    }

    return caculation(numbers: numbers, target: target, index: index + 1, sum: sum + numbers[index]) + caculation(numbers: numbers, target: target, index: index + 1, sum: sum - numbers[index])

}

func solution(_ numbers: [Int], _ target: Int) -> Int {
    return caculation(numbers: numbers, target: target, index: 0, sum: 0)
}

이 분은 답을 다른 방식으로 도출하였다.

함수 자체의 return 값을 주어서 반복문이 끝난 합이 target과 같다면 1를 출력하는데, 해당 1을 다른 변수에 더하지 않고,

재귀함수끼리 더하여 답을 도출하였다.