programmers) 타겟 넘버 | 두번째풀이

프로그래머스 타겟 넘버, DFS로 모든 경우 탐색하기

3주 전에 풀었던 프로그래머스의 타겟 넘버 문제를 다시 풀어보았다.

👉 처음 풀이  programmers) 타겟 넘버, 재귀 연습하기

 

👉 프로그래머스 타겟 넘버 문제

---

문제 설명

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

총 5가지 방법이 있으므로 정답은 5이다.

---

제한 사항

numbers의 개수는 2개 이상 20개 이하
각 숫자는 1 이상 50 이하
target은 1 이상 1000 이하

입출력 예시는 다음과 같다.

 

numberstargetreturn	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

---

문제 유형 분류

이 문제는 DFS / 완전탐색 문제이다.

각 숫자마다 선택할 수 있는 경우는 두 가지이다.

현재 숫자를 더하는 경우
현재 숫자를 빼는 경우

즉, 모든 숫자에 대해 +, - 두 가지 선택을 끝까지 해보면서 target이 되는 경우의 수를 세면 된다.

---

입력 범위 확인

numbers의 길이는 최대 20이다.

각 숫자마다 +, - 두 가지 경우가 있으므로 전체 경우의 수는 다음과 같다.

2^N

최대 N이 20이면,

2^20 = 1,048,576

약 100만 가지 정도이다.

100만 가지 정도는 DFS로 모두 탐색해도 충분히 가능하다고 판단했다.

---

시간 복잡도 허용선 판단

이 문제는 각 숫자마다 두 가지 선택지가 생긴다.

따라서 시간복잡도는 다음과 같다.

시간복잡도: O(2^N)

처음에는 +, - 두 가지니까 O(2N)처럼 생각할 수도 있지만, 실제로는 숫자가 하나 늘어날 때마다 경우의 수가 2배씩 늘어난다.

그래서 2 * N이 아니라 2^N으로 봐야 한다.

---

사용할 자료구조

별도의 자료구조를 사용하기보다는 재귀 DFS를 사용했다.

재귀 함수에는 현재 인덱스와 현재까지의 합을 넘겨주면 된다.

index: 현재 몇 번째 숫자를 보고 있는지
sum: 현재까지 계산된 합

DFS가 끝까지 내려가면, 즉 모든 숫자를 다 사용하면 sum이 target과 같은지 확인한다.

---

처음 작성한 풀이 방식

처음에는 0번째 숫자를 밖에서 먼저 처리하는 방식으로 풀었다.

dfs(0, numbers[0], numbers, target);
dfs(0, -numbers[0], numbers, target);

이 방식은 0번째 숫자를 더하는 경우와 빼는 경우를 먼저 나눈 뒤 DFS를 시작하는 방식이다.

이후 DFS 내부에서는 다음 인덱스 값을 더하거나 빼면서 탐색했다.

dfs(i + 1, sum + numbers[i + 1], numbers, target);
dfs(i + 1, sum - numbers[i + 1], numbers, target);

이 코드도 정답 풀이가 될 수 있다.

---

내가 작성한 코드

class Solution {
    
    // 자료구조 : DFS
    // 풀이시간 : 25분/30분
    // 공간복잡도 : O(N) // 스택이 쌓인다.
    // 시간복잡도 : O(2^N) // 두 가지 경우 +, -
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        count = 0;
        dfs(0, numbers[0], numbers, target);
        dfs(0, -numbers[0], numbers, target);
        return count;
    }
    
    public void dfs(int i, int sum, int[] numbers, int target) {
        if (i == numbers.length - 1) {
            if (sum == target) {
                count++;
            }
            return;
        }

        dfs(i + 1, sum + numbers[i + 1], numbers, target);
        dfs(i + 1, sum - numbers[i + 1], numbers, target);
    }
}

---

코드 설명

먼저 경우의 수를 저장할 count 변수를 선언했다.

int count = 0;

solution()이 실행될 때마다 혹시 모를 누적을 방지하기 위해 count를 0으로 초기화했다.

count = 0;

그 다음 0번째 숫자를 더하는 경우와 빼는 경우로 DFS를 시작했다.

dfs(0, numbers[0], numbers, target);
dfs(0, -numbers[0], numbers, target);

DFS 내부에서는 현재 인덱스가 마지막 숫자인지 확인한다.

if (i == numbers.length - 1) {
    if (sum == target) {
        count++;
    }
    return;
}

마지막 숫자까지 계산한 상태에서 sum이 target과 같다면 방법의 수를 하나 증가시킨다.

아직 마지막 숫자가 아니라면 다음 숫자를 더하는 경우와 빼는 경우를 각각 탐색한다.

dfs(i + 1, sum + numbers[i + 1], numbers, target);
dfs(i + 1, sum - numbers[i + 1], numbers, target);

---

헷갈렸던 부분: 0번째 값은 언제 더해지는가?

DFS를 더 일반적인 형태로 작성하면 보통 이렇게 시작한다.

dfs(0, 0, numbers, target);

처음에는 이 방식이 조금 헷갈렸다.

sum이 0으로 시작하면 0번째 값은 언제 더해지는지 의문이 들었다.

하지만 DFS 함수 안에서 아래처럼 처리하면,

dfs(index + 1, sum + numbers[index], numbers, target);
dfs(index + 1, sum - numbers[index], numbers, target);

처음 index가 0이므로 실제로는 이렇게 실행된다.

dfs(1, 0 + numbers[0], numbers, target);
dfs(1, 0 - numbers[0], numbers, target);

즉, 0번째 값도 DFS 내부에서 자연스럽게 더하거나 빼게 된다.

내가 작성한 코드는 0번째 값을 solution()에서 먼저 처리했고, 추천되는 방식은 0번째 값도 DFS 내부에서 처리한다는 차이가 있다.

---

더 깔끔한 DFS 형태

현재 풀이도 정답이지만, DFS 기본 형태로는 아래 코드가 더 깔끔하다.

class Solution {
    
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        count = 0;
        dfs(0, 0, numbers, target);
        return count;
    }
    
    public void dfs(int index, int sum, int[] numbers, int target) {
        if (index == numbers.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        
        dfs(index + 1, sum + numbers[index], numbers, target);
        dfs(index + 1, sum - numbers[index], numbers, target);
    }
}

이 방식은 다음 의미가 코드에 바로 드러난다.

index번째 숫자를 더한다.
index번째 숫자를 뺀다.
다음 index로 넘어간다.

처음 숫자만 따로 처리하지 않아도 되기 때문에 DFS 문제에서는 이 형태를 기본 템플릿처럼 익혀두면 좋을 것 같다.

---

시간 복잡도

각 숫자마다 선택지는 두 가지이다.

+ 선택
- 선택

따라서 숫자가 N개라면 전체 경우의 수는 다음과 같다.

2^N

그래서 시간복잡도는 다음과 같다.

시간복잡도: O(2^N)

numbers의 길이는 최대 20이므로 최대 경우의 수는 약 100만 가지이다.

2^20 = 1,048,576

이 정도는 완전탐색으로 해결 가능하다고 판단했다.

---

공간 복잡도

별도의 배열이나 리스트를 만들지는 않았다.

하지만 재귀 DFS를 사용했기 때문에 호출 스택이 쌓인다.

재귀 깊이는 최대 numbers의 길이만큼이므로 공간복잡도는 다음과 같다.

공간복잡도: O(N)

---

복잡도 정리

시간복잡도: O(2^N)
공간복잡도: O(N)

---

예외 케이스

이 문제에서는 numbers의 길이가 최소 2 이상이기 때문에 빈 배열은 고려하지 않아도 된다.

다만 DFS를 작성할 때 인덱스 범위를 주의해야 한다.

내가 작성한 방식에서는 아래처럼 numbers[i + 1]을 사용한다.

dfs(i + 1, sum + numbers[i + 1], numbers, target);
dfs(i + 1, sum - numbers[i + 1], numbers, target);

그래서 반드시 그 전에 마지막 인덱스인지 확인해야 한다.

if (i == numbers.length - 1) {
    ...
    return;
}

이 조건이 없으면 i + 1이 배열 범위를 넘어갈 수 있다.

---

이번 풀이에서 배운 점

이번 문제를 풀면서 DFS의 기본 구조를 다시 연습할 수 있었다.

특히 아래 내용을 정리할 수 있었다.

각 숫자마다 +, - 두 가지 경우가 생긴다.
전체 경우의 수는 O(2^N)이다.
재귀 DFS를 사용하면 공간복잡도는 O(N)이다.
0번째 숫자를 밖에서 먼저 처리할 수도 있고, DFS 내부에서 처리할 수도 있다.
DFS는 보통 dfs(index, sum) 형태로 작성하면 더 깔끔하다.

처음에는 O(2N)처럼 시간복잡도를 생각했지만, 경우의 수가 두 배씩 늘어나므로 O(2^N)으로 보는 것이 맞다.

또 0번째 숫자를 언제 더하는지 헷갈렸는데, dfs(0, 0)으로 시작해도 DFS 내부에서 numbers[0]을 더하거나 빼면서 자연스럽게 처리된다는 점을 이해했다.

---

셀프 체크

왜 처음에 바로 풀지 못했는가?

DFS로 풀어야 한다는 방향은 잡았지만, 재귀 함수의 인자를 어떻게 구성해야 할지 조금 헷갈렸다.

특히 0번째 숫자를 밖에서 먼저 처리할지, DFS 내부에서 처리할지 고민했다.

시간이 부족했는가?

전체 풀이 시간은 25분 정도 걸렸다.

제한 시간 안에는 풀었지만, DFS 구조를 정리하는 데 시간이 조금 걸렸다.

문제 해석을 잘못했는가?

문제 해석 자체는 크게 틀리지 않았다.

각 숫자마다 더하거나 빼는 모든 경우를 탐색해야 한다는 점은 잘 파악했다.

자료구조 선택을 잘못했는가?

자료구조를 따로 사용하는 문제는 아니었고, DFS 재귀를 사용한 선택은 적절했다.

엣지 케이스를 놓쳤는가?

인덱스 범위를 주의해야 했다.

특히 numbers[i + 1]을 사용할 때 마지막 인덱스를 먼저 확인하지 않으면 배열 범위를 벗어날 수 있다.

구현 실수가 있었는가?

처음에는 value라는 파라미터를 넘겨놓고 실제로 sum에 반영하지 않는 실수가 있었다.

이후 value 파라미터를 제거하고 sum만 넘기는 방식으로 수정하면서 코드가 더 단순해졌다.

시간 복잡도 판단을 잘못했는가?

처음에는 O(2N)이라고 적었지만, 실제로는 O(2^N)이 맞다.

각 숫자마다 경우의 수가 2배씩 늘어나기 때문이다.