[Programmers] 타겟 넘버 - kotlin

타겟 넘버 (Level2)

link - https://programmers.co.kr/learn/courses/30/lessons/43165

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

 

1. 문제 파악하기

- 입력 :

numbers :  정수형 배열

target : 만들고자하는 정수

numbers 배열내의 정수를 모두 활용하고, +/- 연산만 활용하여 target 정수를 만들수 있는 경우의 수를 구한다.

 

- 출력 :  모든 가능한 경우의 수 

 

2. 아이디어

- DFS를 활용하여 완탐한다

- DFS함수 (현재 타겟 index, 지금까지만들어진 정수의 합, 이번 deeps에서 실행할 연산자 종류)

- 종료조건 : 현재 타겟 index가 주어진 정수 배열의 size인 경우 (모두 다 돌았음)  
                   마지막에 가서 체크하니까  현재 deeps로 도달할때 +, - 인경우가 둘다 카운트가 돼서 결과를 /2 해야정답이다

 

3. 풀이

class Solution {
    var numbers_ = IntArray(0 , {0})
    var target_ = 0
    var oper_ = arrayOf(0, 1) // 0 + / 1 -
    var result = 0
    
    fun solution(numbers: IntArray, target: Int): Int {
        numbers_ = numbers
        target_ = target
        
        dfs(0, 0, oper_[0])
        dfs(0, 0, oper_[1])
        
        return result/2
    }
    
    fun dfs(nextIndex: Int, sum: Int, oper: Int) {
        if(nextIndex == numbers_.size) {
            if(sum == target_) {
                result++    
            }
            return 
        }
    
        if (oper == 0) {
            dfs(nextIndex+1, sum + numbers_[nextIndex], oper_[0])
            dfs(nextIndex+1, sum + numbers_[nextIndex], oper_[1])
        } else {
            dfs(nextIndex+1, sum - numbers_[nextIndex], oper_[0])
            dfs(nextIndex+1, sum - numbers_[nextIndex], oper_[1])
        }
    }
}