[프로그래머스] (JavaScript) 타겟 넘버 - DFS

[프로그래머스] (JavaScript) 타겟 넘버 - DFS

문제 설명

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 함

---

정답 코드

function solution(numbers, target) {
    let answer = 0;

    const dfs = (idx, curN) => {
        if (idx == numbers.length) {
            curN == target && answer++;
            return;  
        } 
        
        dfs(idx + 1, curN + numbers[idx]);
        dfs(idx + 1, curN - numbers[idx]);
    }
    dfs(0, 0)
    return answer;
}

---

코드 풀이

const dfs = (idx, curN) => {
//  if (idx == numbers.length) {
//      curN == target && answer++;
//      return;  
//  } 
        
    dfs(idx + 1, curN + numbers[idx]);
    dfs(idx + 1, curN - numbers[idx]);
}
dfs(0, 0)

 

dfs 함수는 현재 값 numbers[idx] 를 찾아 줄 idx 와 현재 값 numbers[idx] 를 계산한 현재 누적값인 curN  매개변수로 받는다.

 

하나의 dfs 함수에는 idx + 1로 다음 인덱스 값과, curN 에 현재 값 numbers[idx] 를 더하여 호출한다.

또 다른 dfs 함수에는 idx + 1로 다음 인덱스 값과, curN 에 현재 값 numbers[idx] 를 빼서 호출한다.

 

이렇게 되면 numbers 의 모든 값들이 더해진 경우, 빼진 경우로 나뉘어 dfs 가 각각 호출된다.

 

if (idx == numbers.length) {
    curN == target && answer++;
    return;  
}

 

마지막 idx 값까지 돌다가 idx == numbers.length 가 되면 return 한다.

이때, curN 값이 target 와 같다면 answer 의 값을 증가시키고, 다르다면 아무것도 수행하지 않는다.

---

풀이 상세

모든 방법을 탐색한 뒤 최종 방법의 개수를 구하는 것이므로 DFS 방식으로 풀었다.

 

입출력 예시로 설명해보겠다.

 

numbers : [4, 1, 2, 1]

target : 4

 

첫 번째가 + 4 인 경우만 보면, 

 

DFS(0, 0)

    i DFS(1, + 4)

          ii DFS(2, + 4 + 1)

               iii DFS(3, + 4 + 1 + 2)

                    iv DFS(4, + 4 + 1 + 2 + 1) → idx 4 return, curN == target [조건 X]

                    iv DFS(4, + 4 + 1 + 2 - 1) → idx 4 return, curN == target [조건 X]

               iii DFS(3, + 4 + 1 - 2)

                    v DFS(4, + 4 + 1 - 2 + 1) → idx 4 return, curN == target [조건 O] → answer++

                    v DFS(4, + 4 + 1 - 2 - 1) → idx 4 return, curN == target [조건 X]

           ii DFS(2, + 4 - 1)

                    vi DFS(3, + 4 - 1 + 2)

                         vii DFS(4, + 4 - 1 + 2 + 1) → idx 4 return, curN == target [조건 X]

                         vii DFS(4, + 4 - 1 + 2 - 1) → idx 4 return, curN == target [조건 X]

                    vi DFS(3, + 4 - 1 - 2)

                         viii DFS(4, + 4 - 1 - 2 + 1) → idx 4 return, curN == target [조건 O] → answer++

                         viii DFS(4, + 4 - 1 - 2 - 1) → idx 4 return, curN == target [조건 X]

     i DFS(1, - 4)...

 

+ 4인 경우까지만 보면 총 2가지인 것을 알 수 있다.