[프로그래머스] 타겟넘버 JS 풀이

1. 문제설명

문제 설명

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 합니다.

2. 나의 풀이

2-1) 문제 정의와 나의 풀이

<문제 정의>

1. 모든 경우를 빠짐없이 탐색해야 하는 경우인지를 확인
2. 맞다면, DFS 알고리즘을 활용해보자.
3. numbers 배열의 요소마다 앞에 + 또는 -를 붙여 target이 되는 경우의 수를 파악하는 문제.
4. 결국 모든 경우를 빠짐없이 탐색하는 과정이다. 재귀함수를 이용하여 문제 상황에 맞는 DFS 알고리즘을 만들자.

function solution(numbers, target) {
    // 결과값 초기상태
    let count = 0;
    // 각 numbers 요소를 더하고 빼는 과정 중의 합계(sum)와 각 numbers 요소를 더하고 뺀 횟수(depth)를 매개변수로 하여 모두 더하고 뺀 결과가 target인지 확인하는 함수
    function dfs(sum, depth){
        // 모두 더하고 뺏다면 return
        if(depth === numbers.length){
            // 모두 더하고 뺏는데, 그 값이 target과 같은 경우 결과값 + 1
            if(sum === target){
                count++
            }
            return 
        }
        // 각 number 요소를 더하고, 더한 횟수를 1 증가시킨 값을 전달인자로 재귀함수 실행
        dfs(sum + numbers[depth], depth+1)
        // 각 number 요소를 빼고, 뺀 횟수를 1 증가시킨 값을 전달인자로 재귀함수 실행
        dfs(sum - numbers[depth], depth+1)
    }
    
    // 초기 상태부터 dfs 함수 시작
    dfs(0,0)
    
    // 최종 결과값 return
    return count
}

2-2) 나의 풀이 채점결과

3. 다른 사람의 풀이

3-1) 다른 사람의 풀이

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;
}

3-2) 다른 사람의 풀이 채점 결과

4. 느낀 점

<나의 풀이와 달랐던 점>

• 사실 이번 나의 풀이는 다른 사람의 풀이를 보고 푼 풀이이다. DFS 개념이 아직 어려웠고, 왜 재귀함수 풀이가 DFS의 개념이 들어가 있는 것인지 잘 이해하지 못했다.
• 힙(Heap)과는 다르게 DFS는 요령이 있다.
• DFS라고 해서 그래프 자료구조를 외워서 할 필요가 전~~~혀 없었다. DFS는 정말 다양하게 풀이할 수 있다. DFS 개념만 익히고 적절히 문제에 적용시킬 수 있어야 한다.
• 내가 DFS 구조를 이해하기 가장 쉬웠던 방법은 의사코드(pseudo code)로 이해해보는 방법이었다. 이를 통해 가장 쉽게 DFS를 이해할 수 있었다.
• DFS를 구현하는 방법에는 스택을 이용하여 구현하는 방법과 재귀함수를 이용하여 구현하는 방법 등이 있다. 나는 재귀함수를 이용하여 푸는 것이 훨씬 편했다.
• DFS를 이해하기 위해 도움을 받았던 글의 출처를 공유합니다.(1. [알고리즘] 깊이 우선 탐색(DFS)이란, heejeong Kwon / 2.[알고리즘] JavaScript로 구현하는 DFS, Kihoon)