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

https://programmers.co.kr/learn/courses/30/lessons/43165?language=swift 

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

 

DFS로 풀 수 있는 문제. 

 

배열의 원소들을 +, - 조합하여 원하는 target의 수를 만드는 경우의 수가 몇 개인지 세는 문제이다. 

즉 무슨말이다? 

그래프를 따라 쭉 내려가며 일정 "깊이"에 다다랐을 때 원하는 값인지 체크하고 아니면 다른 케이스를 살피는 전형적인 DFS문제이다. 

 

하지만.. 처음에 DFS로 접근하지는 않고 완전탐색? bfs? 형태로 풀이했다. 

 

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    // +첫 원소, -첫 원소 저장
    var result = [numbers[0], -numbers[0]]
    
    // 1번째 원소부터
    for i in 1..<numbers.count {        
        var next = numbers[i]
        var temp = [Int]()
        // 이전 값 + 다음 값, 이전 값 - 다음 값을 배열에 저장
        for res in result {
            temp.append(res + next)
            temp.append(res - next)
        }
        // 배열을 업데이트 
        result = temp
    }
    return result.filter {$0 == target}.count  
}

 

계속 배열에 가능한 경우의 수를 쌓아가는 방식이다. 

계산한 값으로 업데이트 하고 다시 본인을 기준으로 돌며 계산하며 반복해준다.

 

DFS로 풀 때도 위와 유사하긴 하다. 

 

import Foundation

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

func dfs(_ nums: [Int], _ index: Int, _ sum: Int, _ target: Int) -> Int {
    // index가 배열의 길이와 같다면, 다 계산한 것임
    if index == nums.count {
        // 계산한 합이 target과 같다면 1 추가 아니면 0
        return sum == target ? 1 : 0
    }
    // 다음 값을 +하는 경우, -하는 경우에서 발생할 수 있는 경우의 수를 더해준다. 
    return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target)
}

다음 값을 + 해줄 때와 - 해줄 때를 구분하여 구해야 한다. 

index가 배열의 길이와 같아진다면 탈출! 

 

위 두 개의 풀이 모두 개념은 똑같으나 방법이 다르기만 한 것 같다. 

 

끄읕