프로그래머스 / Level 2 , 깊이/너비 우선 탐색(DFS/BFS) , 타겟 넘버 자바스크립트 , JS

프로그래머스 / Level 2 , 깊이/너비 우선 탐색(DFS/BFS) , 타겟 넘버 자바스크립트 , JS

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
2^배열의 크기만큼의 연산이 수행되어서 이 풀이로 접근하면 틀릴거라 생각했는데 잘돌아갔다. 일단 우선해보자.

 

 

문제 출처

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

프로그래머스

 

 

풀이

 

0번 인덱스부터 차례대로 더해가면서 재귀적으로 모든 경우들을 탐색한다.

 

각 배열 요소당 나올수 있는 수 는 +- 각각 두가지 이다.

 

배열요소당 2개씩이니까 요소가 늘어날수록 2^(요소갯수) 만큼의 경우의 수들을 확인해주어야한다.

 

idx 변수를 초기값 0으로 잡고 값이 하나씩 커지게하여 재귀적으로 호출한다.

 

최종적으로 배열의 크기와 같아질 경우 확인해야될 경우에 도달한 것으로 원하는 target 값과 같은지 비교해주고 같다면 카운트해준다.

 

 

 

 

 

 

 

정답

 

function solution(numbers, target) {
  let cnt = 0;
  const check = (idx, T, nums) => {
    if (idx === nums.length) {
      if (T === target) cnt += 1;
      return;
    }
    check(idx + 1, T + nums[idx], nums);
    check(idx + 1, T - nums[idx], nums);
  };

  check(0, 0, numbers);
  return cnt;
}