DFS/BFS-Level2-타겟 넘버(Java,C++,Python,Javascript)

설탕유령·2022년 9월 16일

[문제 설명]

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
[4, 1, 2, 1]	4	2

공통로직

첫번째 노드부터 마지막 노드까지 반복되며 계산이 진행된다.
계산이 완료된 시점(마지막 노드가 연산 된 이후)에 결과값을 판별한다.

Python

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

예시로 제공되는 solution 함수 자체를 재귀 해준다.
만약 numbers가 비어있고(비어있는 경우 false가 리턴되지만 not으로 true로 반전시킴)
target의 값이 0이라면 1을 return한다.
만약 numbers가 비어있는 경우(+첫번째 if에서 검증 했듯이 target이 0이 아닌 경우) 계산이 완료됬지만 target이 일치하지 않는 실패한 연산임으로 0을 return
모든 경우가 아니라면, 즉 numbers에 요소가 존재해 아직 계산할 것이 남아있다면
solution을 다시 호출해 재귀를 발생시킨다.
넘겨줄 numbers는 인덱스 슬라이싱을 통해 첫번째 요소를 제외한 나머지를 전달한다.
target을 넘겨줄 때 2가지 버전이 존재한다. numbers에 첫번째 요소를 더하는 함수와 빼주는 함수를 함수를 각각 호출하고 그 결과값을 더해준다.
호출이 return을 통해서 일어났고, 호출된 결과를 + 더해주는 연산을 진행했기 때문에 return 1 즉, 연산이 완료되고 target이 0이되어 제대로 계산된 경우의 수가 재귀적으로 반환이 되어 더해진다.

C++

#include <string>
#include <vector>

using namespace std;

int total;

void DFS(vector<int> &numbers, int &target,int sum,int n) {
    if(n >= numbers.size()){
        if(sum == target) total++;
        return;
    }

    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}

solution에서 재귀함수용으로 선언된 DFS 함수를 호출한다.
numbers와 target은 주소 값을 복사해 참조하는 방식으로 사용된다.
DFS의 시작은 검증부터 진행된다.
n을 numbers와 비교해 범위를 넘어선 경우 별도 처리를 진행한다.
if문을 통해서 sum이 target과 일치하는 경우 즉 연산이 정상적으로 이루어진 경우 전역 변수인 total의 숫자를 1 올려준다.
if 검증이 완료되고 해당되지 않는 경우 즉, n(인덱스로 활용되는 변수)가 아직 전체 요소의 크기보다 작아 아직 연산이 더 가능한 경우 재귀 함수를 다시 호출해 준다.
함수 호출시에 numbers와 target은 주소값을 전달하는 것으로 참조하는 방식으로 전달된다.
sum 값에 대해서는 현재 참조하고 있는 인덱스인 n을 기준으로 현재 요소를 꺼내와 더해주고 빼준 채로 호출을 한다.
재귀 함수 처리가 완료되면 answer에 전역변수 total에 대한 정보를 넣어준다.

Java

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

재귀를 위한 dfs함수를 만들어 준다.
solution에서 dfs를 호출하고 그 결과값을 answer에 담아준다.
dfs에서는 처음 if에 대한 검증을 통해 현재 index(변수 n)가 마지막인지를 확인한다.
index(변수 n)이 numbers의 길이와 일치하는 경우 if를 통해 연산 결과가 target과 일치하는지 확인한다.
일치하는 경우 1을 return하고, 그렇지 않은 경우 0을 return한다.
index 검증을 해서 아직 연산되어야 할 요소가 남은 경우
dfs를 다시 호출하며, n+1을 통해 index를 증가시키고, + 더하는 경우와 - 빼는 경우를 둘다 호출해 두 함수 호출 결과를 더해준다.
결과적으로 answer = dfs()에는 모든 경우에 수를 검사해 정상적인 연산이 되어 1이 return되는 경우의 수를 합산해 담아준다.

Javascript

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0,0);
    function getAnswer(x,value) {
        if(x<numbers.length){
            getAnswer(x+1,value + numbers[x]);
            getAnswer(x+1,value - numbers[x]);
        } else{
            if(value === target){
                answer++
            }
        }
    }
    return answer;
}

재귀를 위한 함수를 선언해주고 호출해 준다. (getAnswer)
현재 index 값과 더해준 결과만을 매개변수로 받는다.
javascript에 렉시컬 스코프를 이용해 재귀함수 내부에서 외부에 존재하는 numbers와 target을 참조해 연산이 진행된다.
if를 통해 현재 index가 검사 대상의 전체 길이를 넘지 않은 경우 getAnswer 함수를 다시 호출해 준다.
index(변수 x)를 증가시키고, 더하는 경우와 빼는 경우를 둘다 호출한다.
index가 길이를 넘어서 전체 연산이 끝난 경우, if를 통해 현재 값과 target을 비교해 일치하는지 확인한다.
일치하는 경우 연산이 제대로 진행 된 것임으로 외부에 존재하는 answer 변수를 참조해 값을 1 올려준다.