[알고리즘] 프로그래머스 - 타겟넘버

이번주에 코딩테스트가 예정되어 있다. 그래서 예전의 감각을 되살리려고 DFS, BFS 문제를 연습중이다.

오늘 포스팅은 그중에서도 프로그래머스의 '코딩테스트 고득점 Kit' 중 DFS/BFS 색션에 있는 타겟넘버를 정리해 보았다.

참고로 주로 사용하는 언어가 Kotlin 이기에, 당연히 Kotlin으로 문제풀이를 진행했다.

 

문제

문제 설명

배열로 주어진 numbers에서 +,- 의 경우의 수를 모두 구해서 마지막 결과값이 target과 동일한 가짓수를 구하는 경우이다.

 

접근방법

DFS를 이용하여 해결했다. DFS를 이용한 사유는 아래와 같다.

• 주어지는 숫자 개수가 20개 이하여서 재귀로 돌려도 충분한 시간복잡도가 나온다.
• BFS로 해도 상관없지만, DFS를 더 좋아한다.

 

정답코드

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        return go(numbers, target, 0, 0)
    }

    //타겟 넘버
    //dfs로 진행하며, 모든 타겟 넘버들을 다 볼거다 경우를
    //이때 깊이 먼저 탐색해서 하나하나 가지 처나가기를 진행할것이다.
    private fun go(numbers: IntArray, target: Int, currentNumber: Int, currentIdx: Int): Int {
        //numbers -> 원래 맵
        //target -> 만들기 원하는 수
        //currentNumber -> 현재까지 만들어진 수
        // currentIdx -> 끝까지 안가고 numbers.size 만큼 탐색 진행
        if (numbers.size == currentIdx) {
            return if (currentNumber == target) 1 else 0
        }

        return go(
            numbers,
            target,
            currentNumber + numbers[currentIdx],
            currentIdx + 1
        ) + go(
            numbers,
            target,
            currentNumber - numbers[currentIdx],
            currentIdx + 1
        )
    }
}

 

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43165 (프로그래머스 - 코딩테스트 연습(타겟 넘버))