프로그래머스 코딩테스트 연습 Level 2 - 타겟 넘버 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 타겟 넘버 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중 깊이/너비 우선 탐색(DFS/BFS) 관련 문제인,

[타겟 넘버] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

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

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

 

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

작성한 답

solution.js

function solution(numbers, target) {
    let answer = 0;
    const length = numbers.length;
    
    const calc = (depth, ac) => {
        if(depth < length) {
            calc(depth + 1, ac + numbers[depth]);
            calc(depth + 1, ac - numbers[depth]);   
        } else {
            if(ac === target) {
                answer++;
            }
        }
    }
    
    calc(0, 0);
    
    return answer;
}

 

설명

모든 숫자를 더하거나 빼는 경우의 수를 탐색할 수 있는 DFS를 사용하여 문제를 해결할 수 있습니다!

calc(depth, ac) 라는 계산하는 깊이와 누산되는 값을 사용하는 함수를 하나 만듭니다.
해당 함수는 numbers 배열에 있는 모든 숫자를 더하거나 뺄 때 까지 재귀적으로 사용하도록 합니다.

depth 매개변수에 몇번째 index 까지 계산을 하였는지를 담고,

아직 depth가 numbers 배열의 길이보다 작다면 numbers 배열 안의 모든 숫자를 계산하지 않았다는 의미이기 때문에

ac 매개변수에 0번째 index 부터 더하거나 빼서 누산된 값을 담아 재귀적으로 호출하다가,

depth 가 numbers 배열의 길이와 같아졌을 때, 누산된 값이 타겟 넘버(target)와 같다면

answer을 증가시켜 타겟 넘버가 되는 방법의 개수를 증가시켜 방법의 가지 수를 구하고,

해당 값을 반환하는 것으로 문제를 해결할 수 있습니다.

 

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.