프로그래머스 lv2 - 타겟넘버(Kotlin)

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

프로그래머스

문제 접근

• 주어진 수들을 더하거나 빼서 target넘버를 만드는 경우의 수를 구하는 문제
• dfs를 재귀함수로 구현하여 배열안의 값을 하나씩 더하거나 빼서 target과 같으면 경우의 수를++해주는 식으로 구현함

1. 경우의 수 계산

최악의 경우에 수행할 연산 횟수를 계산해서 재귀함수/완전탐색을 사용해도 될지 확인

시간복잡도

numbers의 최대 개수는 20개 이고 한 개당 가능한 경우의 수는 2가지(더하거나 빼거나)이므로 최악의 경우의 수는 2^20이다.(완전탐색 가능, 2^20==100만 < 500만)

 

2. 수행동작

재귀함수가 호출됐을 때 한 턴마다 수행할 동작 구현

 

3. 탈출조건

어느 시점에 이 재귀함수를 끊을 지 구현

 

정답 코드

class Solution {
    fun solution(numbers: IntArray, target: Int): Int {
        var answer = 0
       
        fun dfs(index:Int, temp:Int){
            //모든 인덱스를 진행해서 target과 비교
            if(index < numbers.size-1)
            {
                //주어진 수를 더하고 빼봄
                dfs(index+1, temp+numbers[index])
                dfs(index+1, temp-numbers[index])
            }
            else 
            {
                if(temp+numbers[index] == target || temp-numbers[index] == target){
                    answer++
                }
            }
        }
        dfs(0,0)
        return answer
    }
}

 

 

이 문제에서 재귀함수의 동작원리

• 아직 재귀함수가 어떻게 돌아가는지 잘 이해가 안되어서 이 문제에서의 재귀함수 동작과정을 내가 컴파일러가 됐다고 생각하고 하나씩 정리해보았다...
• 위 코드를 정리해보면 index가 number.size와 같으면 return하고 이때 temp와 target이 같으면 answer를 1증가한다.
• 요소 별로 더하기 빼기를 해줘야 하기때문에 dfs를 2번 재귀시켰다.

 

동작과정

• dfs(index+!, temp+numbers[index)를 a, dfs(index+1, temp-numbers[index])를 b라고 하여 진행하겠다.
• numbers는 [1,1,1]이고 target은 1이라 가정하겠다.

1. dfs(0,0) : index, temp가 0인 채로 dfs에 접근한다.
2. dfs(1,1) : a를 진행하여 index와 temp가 1씩 증가했다(진행과정 : a)
3. dfs(2,2) : a를 진행하여 index와 temp가 1씩 증가했다.(a-a)
4. dfs(3,3) : a를 진행하여 index와 temp가 1씩 증가했다.(a-a-a)
5. 다음 call에서 a를 진행하려 했으나 index == number.size이므로 종료됩니다.(answer = 0, target != temp)
6. dfs(2,2) : a가 종료되고 b를 실행시키는데 이때, index는 number.size보다 1작은 2부터 시작한다.(a-a)
7. dfs(3,1) : b를 진행해 index가 1증가하고 temp는 1 감소하였다.(a-a-b)
8. 이때 index == numbers.size이고 temp == target이므로 answer를 1 증가한다.
9. dfs(2,0) :  2번에서 a다음 a를 진행했으므로 이번엔 a다음 b를 진행한다.(a-b)
10. 위처럼 a와 b의 경우를 모두 진행해보고 index == numbers.size면 return, 이때 target == temp면 answer++을 진행하는 방식이다.
11. 한마디로 재귀함수는 a-a-a, a-a-b, a-b-a, a-b-b, b-a-a, b-a-b, b-b-a, b-b-b의 경우의 수를 모두 실행하고 마무리된다. 

 

 

 

좋은 강의 영상

https://www.youtube.com/watch?v=S2JDw9oNNDk&list=PLlV7zJmoG4XI9VguUVNMu3pCjssb4aR_0&index=13