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

문제



주어진 숫자배열에 적절한 부호를 붙혀 연산하여 target숫자가 될 수 있는 경우의 수를 구하는 문제이다.

---

풀이

문제의 조건에 숫자배열의 순서를 바꾸지 말라는 조건이 있다.

따라서 각 숫자를 재귀하여 탐색하는 DFS를 사용하여 문제를 해결하였다.

 

 fun DFS(idx: Int, _summ: Int, isPlus: Boolean) {
            var _sum = _summ
            if (isPlus) {
                _sum += numbers[idx]
            } else {
                _sum -= numbers[idx]
            }
            if (idx == length - 1) {
                if (_sum == target) {
                    cnt ++
                }
                return
            }
            
            
            DFS(idx+1, _sum, true)
            DFS(idx+1, _sum, false)
            
            return
        }

DFS의 구현은 다음과 같다.

먼저 현재 숫자배열의 위치, 이전까지의 합, 음수 양수 여부를 인자로 받는다.

함수는 먼저 음수 양수 여부를 판단하여 부호를 붙혀 연산을한다.

이 후 해당 배열이 마지막까지 도달하였으면 target과 숫자가 일치하는지 판단하고

일치하면 cnt를 증가시켜주고 return하고 일치하지않으면 그냥 return한다.

만약 배열의 끝까지 도달하지 않은 상태이면 음수 양수 각각의 DFS를 호출하고 return한다.

DFS(0, 0, true)
DFS(0, 0, false)

시작부분은 0번째 인덱스의 양쪽 부호 모두를 호출하는 것으로 시작한다.

---

코드

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
        var cnt = 0
        val length = numbers.size
        
        fun DFS(idx: Int, _summ: Int, isPlus: Boolean) {
            var _sum = _summ
            if (isPlus) {
                _sum += numbers[idx]
            } else {
                _sum -= numbers[idx]
            }
            if (idx == length - 1) {
                if (_sum == target) {
                    cnt ++
                }
                return
            }
            
            
            DFS(idx+1, _sum, true)
            DFS(idx+1, _sum, false)
            
            return
        }
        
        DFS(0, 0, true)
        DFS(0, 0, false)
        
        
        return cnt
    }
}