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

Programmers : 타겟 넘버

 

🔗 문제 링크

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

프로그래머스

 

---

💬 문제

 DFS(깊이 우선 탐색) 에 대한 이해가 있다면, 충분히 풀 수 있는 문제였다.

DFS에 대해 잘 모른다면, 아래 글을 먼저 보고 오는걸 추천한다.

https://valueengine.tistory.com/48

[알고리즘] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

 

1. n개의 정수가 담긴 배열 numbers가 주어져있고, 이 정수들을 더하거나 빼서 타겟 넘버(target)를 만들어야 한다.
   
   
2. 이 과정을 통해 타겟 넘버를 만들 수 있는 경우의 수 answer를 출력해준다.

 

728x90

 

---

👣 예제를 참고한 풀이

예제 입력

numbers : [1, 1, 1]
target : 3

 

 

1이 3개가 주어지고, 타겟 넘버가 3일때, 타겟 넘버가 될 수 있는 경우의 수는 세 가지다.

이때 처음에 sum이 0일때가 정점의 시작이고, 배열의 인덱스(idx)가 깊이(depth)가 된다.

 

 

---

🔑 풀이

• dfs 함수는 0번째 인덱스부터 각 정수를 더하거나 빼서 그 합 sum을 누적해준다.
  
  - 수행 동작에는 인덱스 값이 증가할 때마다, 그 인덱스의 정수를 더하거나 빼주는 2가지 경우가 있다.
  
  
• 수행 동작은 배열에 있는 정수 n개 만큼만 진행되어야 한다.
  
  - 따라서 현재 인덱스번호가 배열의 길이랑 동일하면, 더 이상 수행 동작을 할 정수가 없기에 탈출을 해준다.
  
  - 우리가 찾는 target 값과 최종적으로 누적된 sum이 동일하다면, answer의 개수를 늘려준다.

function solution(numbers, target) {
    let answer = 0;
    const len = numbers.length;
    
    function dfs(idx, sum) {
        // 1. 탈출 조건
        if (idx === len) {        // 현재 인덱스가 배열 마지막 값에 왔을 때
            if (target === sum) {
                answer++;
            }
            return;
        }
        // 2. 수행 동작
        dfs(idx + 1, sum + numbers[idx]);  // 더할 경우
        dfs(idx + 1, sum - numbers[idx]);  // 뺄 경우
    }
    dfs(0, 0);
    return answer;
}

 

반응형

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️