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

재귀를 이용한 문제 풀이 

fun solution(numbers: IntArray, target: Int): Int {
    var answer=0
    fun dfs(index: Int, currentSum: Int) {
        if (index == numbers.size) {
            if (currentSum == target) {

                answer = answer + 1
            }
        } else {
            val add = dfs(index + 1, currentSum + numbers[index])
            val subtract = dfs(index + 1, currentSum - numbers[index])
        }
    }
    dfs(0, 0)
    return answer
}

 

간단한 시나리오 예시

numbers = intArrayOf(1, 2), target = 1 일 경우 numbers 배열은 [1, 2]이고, 목표 값 target은 1입니다.

전체 실행 트리

시나리오 결과 : 경우의 수는 1개로  answer 값은 1 

스택(리스트)을 이용한 문제 풀이

fun solution(numbers: IntArray, target: Int): Int {
    val stack = mutableListOf<Pair<Int, Int>>() // (index, currentSum)
    stack.add(Pair(0, 0)) // 초기 상태 추가
    var count = 0

    while (stack.isNotEmpty()) {
        val (index, currentSum) = stack.removeAt(stack.size - 1)

        if (index == numbers.size) {
            if (currentSum == target) {
                count++
            }
        } else {
            stack.add(Pair(index + 1, currentSum + numbers[index]))
            stack.add(Pair(index + 1, currentSum - numbers[index]))
        }
    }

    return count
}

 

느낀점 : DFS 풀이 방법은 재귀, 스택 두가지 방법이 있지만 재귀로 코드를 구성하는 게 항상 어려운 것 같다. 

문제를 많이 풀어보고 익숙해 지도록 노력해야겠다.