[프로그래머스_자바스크립트] Lv2. 타겟 넘버 / DFS, 깊이 우선 탐색

 

[Javascript_ 타겟 넘버]

 

---

 

<STUDY>

 

📢 문제 📢

 

n개의 음이 아닌 정수들이 있습니다.

이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

 

사용할 수 있는 숫자가 담긴 배열 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

 

 

❗아이디어

 

   - 깊이 우선 탐색을 이용하여 모든 경우의 수를 확인한다.

 

 

---

 

<전체 코드>

 

function solution(numbers, target) {
  const n = numbers.length;
  let answer = 0;
  let check = new Array(n);

  function DFS(index) {
    if (index === n) {
      let operate = 0;
      for (let i = 0; i < n; i++) {
        check[i] === "+" ? operate += numbers[i] : operate -= numbers[i];
      }
      operate === target && answer++;
    } else {
      check[index] = "+";
      DFS(index + 1);
      check[index] = "-";
      DFS(index + 1);
    }
  }

  DFS(0);
  return answer;
}

 

---

 

<코드 설명>

 

☝ + or - 를 확인할 check 배열 만들기

 

let check = new Array(n);

 

✌ DFS 함수 만들기

 

function DFS(index) {
    if (index === n) {
      let operate = 0;
      for (let i = 0; i < n; i++) {
        check[i] === "+" ? operate += numbers[i] : operate -= numbers[i];
      }
      operate === target && answer++;
    } else {
      check[index] = "+";
      DFS(index + 1);
      check[index] = "-";
      DFS(index + 1);
    }
  }

 

   - 마지막에 계산한 값을 나타낼 operate 변수를 생성한다.

   - index가 numbers의 길이와 같지 않은 경우 +와 -를 나누어 호출한다.

   - index가 numbers의 길이와 같아지면 check 배열에 따라 값을 계산하고 target과 동일한 경우 answer를 1씩 증가시킨다.

 

 

---

🔆프로그래머스 Lv2. 타겟 넘버🔆

 

👉ez1n github 구경하기👈

 

ez1n - Overview