문제

문제 설명
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
입출력 예 설명
문제에 나온 예와 같습니다.

코드

public class Level2_2 {
    public static void main(String[] args) {
        Level2_2 l = new Level2_2();
        int[] numbers = {1,1,1,1,1};
        int target = 3;
        int solution = l.solution(numbers, target);
        System.out.println("solution = " + solution);
    }

    static int answer;
    public int solution(int[] numbers, int target) {
        //dfs 탐색을 통하여 문제를 풀이해야함...
        dfs(0,0,numbers,target);
        return answer;
    }
    public void dfs(int level, int sum, int[] numbers, int target){
        if(level == numbers.length){
            if(sum == target) answer++;
        }else{
            dfs(level+1, sum+numbers[level], numbers, target);
            dfs(level+1, sum-numbers[level], numbers, target);
        }
    }
}

설명

문제에 대한 이해를 먼저 하면 배열에 들어와 있는 랜덤한 수(제한 사항에 위반하지 않는 수의 범위)들을 모두 더하거나 뺏을 때 target의 값과 동일한 경우가 몇개인지 카운트하는 문제였다.

내가 문제를 풀수 있었던 개념은
더한다는 +의 자식 노드와
뺀다는 -의 자식 노드 2개의 자식 노드를 가지게 되는 트리구조를 갖고 문제를 풀이하려고 했고(=이진 트리 구조) 그 구조가 맞았던것 같다.

dfs 내부의 로직만 살펴보면

첫 조건문인

if(level == numbers.length){
    if(sum == target) answer++;
}

level이 탐색 깊이에 맞는지 확인하는 코드다. 탐색하려는 깊이에 맞다면 다시 그 값이 우리가 원하는 target 값인지 체크한 뒤 answer을 증가시켜주는 로직이고

다음으로

else{
    dfs(level+1, sum+numbers[level], numbers, target);
    dfs(level+1, sum-numbers[level], numbers, target);
}

이 부분이 이진트리 형식으로 뻗어나갈 수 있도록 해주는 로직이다. 위에 dfs가 더했을 때를 구현해주는 부분이고 아래 dfs는 뺏을 때를 구현해주는 부분이다.

dfs 강의를 들으면서 풀면서 이전에 프로그래머스에서 못풀었던 문제중에 비슷한 유형의 문제가 생각나서 다시 풀어봤다. 그런데 역시나 이렇게 푸니까 풀리는구나...ㅎ 항상 이렇게 해결하지 못하던 문제를 풀어냈을 때 가장 재밌는거 같다

시간 복잡도 계산해보기

알고리즘 문제를 풀다 보면 시간 복잡도라는게 정말 중요하다고 느낀다. 그 이유는 내가 문제를 풀고 있을 때 해당 문제가 1초내로 반환해야 하는 문제일 경우 시간 복잡도를 초과해서 풀고 있다면 그건 잘못된 풀이 방식이란걸 깨달을 수 있고 처음부터 전략을 짤때 알맞은 알고리즘을 갖고 시작할 수 있기 때문이다.
그래서 앞으로는 문제를 풀었을 때 최대한 시간 복잡도도 같이 해결해보려고 노력해보자!

우선 문제를 읽으면서 알수 있는 내용은

주어지는 숫자의 개수는 20개 이하

이 제한은 우리에게 dfs로 문제를 풀이할때 최대 깊이는 20이라는 제한을 알려준다.

그럼 현재 내가 사용한 재귀적 dfs 알고리즘에 대입 했을 때 2^n으로 풀어낼 수 있는데 그 이유는 이진트리로 풀어내기 때문에 dfs가 2방향으로 갈려진다. 그래서 2이고 n은 우리가 넣는 깊이의 수만큼 크기가 정해진다.

그림으로 이해해보면 예를들어 [1,1] 의 값이 들어왔을 때 2^2=4 이다.

그림을 확인하면 리프노드가 4임을 알 수 있다. 만약 노드를 3개로 뻗어간다면 3^n임을 바로 알수 있다.

그리고 이걸 다시 코드로 대입해보면 우리는 dfs()를 호출하여 다시 dfs() dfs() 두개를 얻는다. 이러면 dfs()의 호출을 계속 반복하였을 때 dfs()는 2^n만큼 커지는 것을 알수 있다. 그러면 여기서 dfs()를 내부에서 3번 호출한다면? 3^n만큼 커지는 것이고 4번 호출하면 4^n만큼 커지게된다.

다시 문제로 돌아와서 그럼 이진 트리로 문제를 풀어냈으니 최고 20개의 값이 들어왔을 때 dfs의 시간 복잡도는 2^20이 된다. 2^20 = 2^102^10 이므로 1024 1024 대략 1,000,000ns로 1초가 넘지 않아 풀이가 가능하다.

만약 여기서 내가 풀이하는데 최대의 가짓수로 뻗어갔는데도 문제의 시간 복잡도가 넘어간다면 백트래킹의 조건을 더 자세하게 넣어 최적화하여 문제를 푸는 방법도 고려할 수 있다!