프로그래머스 2단계 - 타겟 넘버

2 단계 : 타겟 넘버

코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버

---

문제 설명

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 = (index, sum) => {
        // 1. 탈출조건
        // numbers.length가 되면 더이상 돌 인덱스가 없기 때문에 종료한다
        // 근데 여기서 sum이 target number 까지 도달했다면 answer을 증가시킨다.
        if(index === numbers.length) {
            if(sum === target) answer++;
            return;
        }
        
        // 2. 수행 동작
        // 수행할 수 있는 동작은 단 두가지, 더하거나 빼거나 다음인덱스에 접근할 때, 더하거나 빼거나 ok?
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
    
    dfs(0,0);
    return answer;
}

리뷰

순서는 다음과 같다
1. 모든 수를 탐색하면서 더하거나 빼봐야겠죠? 후..
2. dfs, bfs를 푸는 전형적인 방법은 재귀를 이용해서 풀어야겠죠?
3. 재귀는 함수안에서 1. 탈출조건 2. 수행동작 2가지를 정의해 줘야합니다.
4. 1. 탈출조건은 모든 인덱스를 돌았을 때 그만 멈춰야합니다. index를 증가시키면서 index가 numbers의 길이가 되면 멈춰야됩니다. 갈데가 없어요
5. 2. 수행동작은 sum = 0을 정의하고 하나는 더해주고 하나는 빼줘야합니다. 더하거나 빼주는 2가지 경우밖에 없으니까요
6. 자 재귀의 탈출조건에 걸렸다면 sum이 target과 같은지 봐야겠죠? 같으면 증가!

총평 : 이런 기법이 들어가기 시작하면 어렵네요

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43165