🕊 Link

Lv2. 타겟 넘버 Javascript
https://programmers.co.kr/learn/courses/30/lessons/43165

🧑🏻‍💻 Code(javascript)

function solution(numbers, target) {
  let answer = 0;
  let count = 0;
  function calc(x, value) {
    if (x < numbers.length) {
      calc(x + 1, value + numbers[x]);
      calc(x + 1, value - numbers[x]);
    } else {
      if (value === target) {
        answer++;
      }
    }
  }
  calc(0, 0);
  return answer;
}

💡 Solution

깊이 우선 탐색(DFS)을 통해 풀이함

function solution(numbers, target) {
  let answer = 0;
  function calc(x, value) {
    if (x < numbers.length) {
      calc(x + 1, value + numbers[x]);
      calc(x + 1, value - numbers[x]);
      // number[x]를 더하는 경우와 빼는 경우를
      // 재귀적으로 호출하여 계속해서 가지를 뻗어 나감
    } else {
      if (value === target) {
        answer++;
      }
      // x의 값이 numbers.length과 같아지면
      // value 값과 target이 같은지 판단해서 count up
    }
  }
  calc(0, 0);
  return answer;
}

🔁 복습 풀이

2021.09.01

function solution(nums, target) {
  let answer = 0;
  const LENGTH = nums.length

  const dfs = (value, depth) => {
    if (depth === LENGTH) {
      if (value === target) answer++
    } else {
      const num = nums[depth]
      dfs(value + num, depth + 1)
      dfs(value - num, depth + 1)
    }
  }

  dfs(0, 0)
  return answer
}

const nums = [1, 1, 1, 1, 1]
const target = 3
console.log(solution(nums, target))

👨🏻‍💻💭 Self Feedback

• DFS는 빠져나갈 조건을 먼저 찾고 중간 과정을 생각.
  마지막 count가 몇인지 헷갈리지 않도록 주의
• numbers.length까지 함수를 호출은 하지만 분기에서 else를 태우기 때문에 x가 5까지 감.

• 2021.06.17 - 최초 작성

댓글 환영 질문 환영
by.protect-me