문제
https://school.programmers.co.kr/learn/courses/30/lessons/43165
풀이
- 모든 가능한 조합을 시도해봐야 한다. numbers 배열의 숫자를 순서대로 + 혹은 -를 해봐야 한다. 마치 각 숫자 노드에 다음 숫자가 +, - 두 가지 버전으로 달려있는 이진트리를 모두 순회하는 경우와 같다.
- 깊이 우선 탐색(DFS) 이므로 dfs라고 함수를 만들고, 다음 인덱스로 넘어가기 위한 index, 합을 축적할 currSum을 마련한다.
- 인덱스와 sum은 0부터 시작하므로 처음에는 dfs(0, 0)로 시작한다.
- dfs의 종료 조건은 index가 numbers.length가 될 때 (배열의 인덱스 범위보다 넘쳤을 때)이다. 이때는 여태가지 축적한 sum이 target과 같은지 검사하고, 맞다면 count++ 해준다.
- dfs 재귀호출에서 인덱스 파라미터는 index + 1로 다음 인자를 호출하고, sum은 sum에 숫자를 더하거나 뺀 두 가지 버전을 준비한다.
- dfs 호출이 모두 끝났으면 count를 반환한다.
function solution(numbers, target) {
let count = 0;
function dfs(index, currSum) {
if(index === numbers.length) {
if(currSum === target) count++;
return;
}
dfs(index + 1, currSum + numbers[index]);
dfs(index + 1, currSum - numbers[index]);
}
dfs(0, 0);
return count;
}
'알고리즘 이론 & 풀이 > 프로그래머스' 카테고리의 다른 글
프로그래머스 Lv.2 | (스택/큐) 기능개발 js (0) | 2023.08.09 |
---|---|
프로그래머스 Lv.1 | (스택/큐) 같은 숫자는 싫어 js (0) | 2023.08.09 |
프로그래머스 Lv.1 | (완전탐색) 모의고사 js (0) | 2023.08.09 |
프로그래머스 Lv.2 | (완전탐색) 소수찾기 js (0) | 2023.08.08 |
프로그래머스 Lv.1 | 전화번호 목록 js (0) | 2023.08.08 |