[Programmers] 코딩테스트 (DFS/BFS) - 타겟 넘버

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

DFS와 BFS를 연습하기 위한 예제 중 하나입니다.

문제에 따르면 Int 배열이 하나 주어지고, target이 주어집니다.

주어진 배열의 각 값들을 + 또는 - 를 했을 때 target과 동일한 값이 몇 번이나 나오는지 확인하는 것입니다.

여기서 DFS를 이용하기 위해서 노드를 그려보면 다음과 같이 그릴 수 있습니다.

이 문제에서의 DFS 그림

시작은 0이고, 입력된 numbers의 0번 인덱스 부터 -와 +를 계산합니다.

가장 마지막 numbers의 element까지 계산을 끝낸 후 target과 같은 것들이 몇개가 있는지 결과를 반환합니다.

 

이번 문제는 세 가지로 풀어봤습니다.

1. 일반적으로 사용하는 것 처럼 dfs함수를 만들고, 그 함수를 이용하여 재귀함수를 구현한 후 결과값 구하기
2. 최대한 축약하되, 추가 parameter없이 재귀함수로 구현한 코드(solution 함수만 이용한)
3. 축약은 하되, 추가 parameter로 Index를 추가하여 재귀함수로 구현한 코드(solution 함수만 이용한)

각각의 계산 시간도 비교를 해보았습니다.

1. DFS함수를 만들고 구현

func solution(_ numbers:[Int], _ target:Int) -> Int {
    //numbers = [1, 1, 1, 1, 1] -> 
    /*
    테스트 1 〉	통과 (41.00ms, 16.4MB)
    테스트 2 〉	통과 (41.15ms, 16.3MB)
    테스트 3 〉	통과 (0.06ms, 16.3MB)
    테스트 4 〉	통과 (0.20ms, 16.2MB)
    테스트 5 〉	통과 (1.29ms, 16.3MB)
    테스트 6 〉	통과 (0.09ms, 16.6MB)
    테스트 7 〉	통과 (0.05ms, 16.6MB)
    테스트 8 〉	통과 (0.34ms, 16.3MB)
    */
    var result: Int = 0
    dfs(index: 0, numbers: numbers, result: &result, sum: 0, target: target)
    return result
}
func dfs(index: Int, numbers: [Int], result: inout Int, sum: Int, target: Int) {
    if index == numbers.count {
        if sum == target {
            result += 1
        }
        return
    }
    
    dfs(index: index + 1, numbers: numbers, result: &result, sum: sum + numbers[index], target: target)
    dfs(index: index + 1, numbers: numbers, result: &result, sum: sum - numbers[index], target: target)
}

dfs라는 함수를 만들고 그 함수 내부에서 다시 dfs를 호출 하는 식으로 재귀함수를 구현했습니다. 

index가 numbers의 갯수와 같은 경우(index == numbers.count)가 될 때 return이 호출되는데, 이 때 sum(이전까지 + 또는 -를 한 것들의 결과값)이 target(solution 함수가 호출 될 때 목표하는 값)과 동일 한 경우에는 count를 올려야 하기 때문에 result에 1을 더해줍니다.

 

2. 축약하되, 추가 Parameter없이 재귀함수로 구현

func solution(_ numbers:[Int], _ target:Int) -> Int {
    /*
    테스트 1 〉	통과 (351.01ms, 16.4MB)
    테스트 2 〉	통과 (354.27ms, 16.5MB)
    테스트 3 〉	통과 (0.37ms, 16.6MB)
    테스트 4 〉	통과 (1.43ms, 16.4MB)
    테스트 5 〉	통과 (10.89ms, 16.3MB)
    테스트 6 〉	통과 (0.72ms, 16.5MB)
    테스트 7 〉	통과 (0.37ms, 16.6MB)
    테스트 8 〉	통과 (2.72ms, 16.2MB)
    */
    if numbers.isEmpty {
        return (target == 0 ? 1 : 0)
    }
    return solution(Array(numbers[1..<numbers.count]), target + numbers[0]) + solution(Array(numbers[1..<numbers.count]), target - numbers[0])
}

이 경우는 파이썬 솔루션을 어쩌다 보게 되어서 Swift로 한 번 줄여보고자 하여 구현한 코드입니다.

"numbers[1..<numbers.count]"는 for i in 1..<numbers.count와 동일한 방식입니다. 따라서 Array로 감싸서 배열로 만들어줘야 합니다.

또한 target의 값에 현재 numbers의 [0]번 값을 더하거나 빼서 solution을 다시 호출합니다.

위의 구문을 반복하면 어느 순간에 numbers.isEmpty가 true가 됩니다.

그 때의 target이 0인지 확인을 합니다.(매번 호출 할 때 numbers의 [0]번 인덱스 값을 더하거나 뺐기 때문에 가능한 것입니다.)

target이 0이면 count를 1 증가시켜줘야 하기 때문에 return 1, 0이 아니라면 무시해야하기 때문에 return 0을 합니다.

 

3. 축약하되, Parameter를 추가하여 재귀함수로 구현

func solution(_ numbers:[Int], _ target:Int, index: Int = 0) -> Int {
    /*
    테스트 1 〉	통과 (31.42ms, 16.4MB)
    테스트 2 〉	통과 (31.35ms, 16.4MB)
    테스트 3 〉	통과 (0.04ms, 16.5MB)
    테스트 4 〉	통과 (0.14ms, 16.3MB)
    테스트 5 〉	통과 (0.99ms, 16.5MB)
    테스트 6 〉	통과 (0.07ms, 16.3MB)
    테스트 7 〉	통과 (0.04ms, 16.4MB)
    테스트 8 〉	통과 (0.27ms, 16.4MB)
    */
    if index == numbers.count {
        return (target == 0 ? 1 : 0)
    }
    return solution(numbers, target + numbers[index], index: index + 1) + solution(numbers, target - numbers[index], index: index + 1)
}

2번과 비슷한 방식이지만, 여기서는 index parameter가 추가됩니다.

이 index parameter에는 default(0)값을 지정하여 가장 처음 solution을 호출하는 부분에서 문제가 발생하지 않도록 해줍니다(Test case들).

이 index는 호출 되었을 때 numbers의 몇 번째 인덱스 값을 이용하여 계산할지 알기 위해서 사용합니다.

따라서 호출 될 때 마다 index + 1을 해줘야 합니다.

그 외의 부분은 2번 방식과 거의 같은데, test 결과에서 속도의 차이가 발생하는 이유는 2번 방식에서 Array(numbers[1..<numbers.count])를 호출하여 매번 새로운 array를 만들어야 하는 것과는 다르게 number[index]를 통해 해당 인덱스를 바로 접근하는 것 때문입니다.

아무래도 for문을 사용하게 되면 data양이 많을수록 느려질 수 밖에 없으니까요.