[프로그래머스] 타겟 넘버 in C++

(제가 생각한 솔루션이므로 최적의 솔루션이 아닐 수 있습니다..! 피드백 환영합니다!)

 

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

1. 문제 이해

문제에서 주어지는 입력값은 총  두 개입니다.

 

입력값 이름	예시	타입	조건
numbers	[1, 1, 2, 2, 3]	vector<int>	2개 이상 20개 이하
target	3	int	1 이상 1000 이하

 

numbers 벡터에 주어진 각 element들을 더하거나 빼서 target 과 같은 숫자를 만들 수 있는 방법의 개수를 구하는 문제입니다.

 

예를 들어 numbers가 [1, 1, 1, 1] 이고 target이 2 인 경우,

1) 1, 1, 1, -1

2) 1, 1, -1, 1

3) 1, -1, 1, 1

4) -1, 1, 1, 1

총 4 가지 방법이 있습니다.

 

2. 풀이법 연상

크게 두 가지 방법이 생각났습니다.

 

하나는 모든 element들을 각각 더하거나 빼는 연산을 하기 위해,

[1, 1, 1, 1, 1]

[1, 1, 1, 1, -1]

[1, 1, 1, -1, 1]

...

[-1, -1, -1, -1, -1]

와 같이 각 element에 1 또는 -1을 곱해줄 벡터들을 만들고, 실제로 곱해줘서 합산하여 target과 같은 경우 카운팅을 하는 방법을 연상했습니다.

 

또 다른 방법은 DFS(Depth First Search)를 이용하는 방법이었습니다.

 

sum이 0인 상태로 시작해서,

numbers의 첫번째 원소부터 차례대로 더하거나 빼는 분기점을 나누게 됩니다.

모든 element를 구하게 된다면, 결국 이진 트리와 같은 구조로 만들어질 것입니다.

 

예를 들어, [1, 2, 3, 4..] 인 numbers가 있다고 하면 DFS를 통해 다음과 같은 트리 구조를 만들 수 있습니다.

 

 

해당 트리의 terminal 노드에 도착한 경우, 지금까지 거쳐온 경로의 모든 노드의 값을 더해서 target 값과 같다면 count + 1을 하도록 할 수 있습니다.

 

3.  풀이에 필요한 지식

DFS (Depth-First-Search) 는 깊이 우선 탐색 알고리즘으로 같은 depth의 노드에 대해서 다른 노드를 탐색하기 이전에 자신의 노드의 아래 노드까지 완벽히 탐색합니다.

 

이와 반대로 BFS (Breadth-First-Search) 는 너비 우선 탐색 알고리즘으로 같은 depth의 노드를 먼저 탐색한 뒤에 아래 depth의 노드들을 탐색한다는 차이가 있습니다.

 

DFS는 스택 또는 재귀 함수로, BFS는 큐 자료구조로 구현할 수 있습니다.

 

DFS는 스택의 top 노드를 탐색하면서 아래 depth의 노드를 top에 계속 push하기 때문에 아래 depth의 노드부터 완전히 탐색될 수 밖에 없지만,

BFS는 큐에 탐색한 노드의 아래 노드들을 push 해도 front에 있는 노드, 즉 같은 depth의 다른 노드들을 먼저 탐색하고 pop을 한 뒤에야 탐색을 하기 때문에 같은 depth의 노드부터 탐색이 가능합니다.

 

4. 코딩

#include <string>
#include <vector>

using namespace std;

int numbers_size;
int count;

void dfs(vector<int> numbers, int target, int sum, int depth){
    if(depth >= numbers_size){ // terminal
        if(sum == target)
            ++count; // target과 같은 경우,
        
        return;
    }
    
    dfs(numbers, target, sum + numbers[depth], depth+1); // 더한 경우,
    dfs(numbers, target, sum - numbers[depth], depth+1); // 뺀 경우, 
};

int solution(vector<int> numbers, int target) {
    int answer = 0;
    numbers_size = numbers.size(); // numbers 개수
    count = 0; // target과 같은 방법의 개수.
    
    dfs(numbers, target, 0, 0); // sum과 depth가 0부터 시작.
    answer = count;
    
    return answer;
}