[JS] 프로그래머스 코딩테스트 연습 | 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

문제링크: 깊이/너비 우선 탐색 > 타겟 넘버

1. 문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

2. 입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

---

3. 풀이

예2 [4, 1, 2, 1]로 그래프를 만들면 다음과 같다

👉 따라서 깊이 우선 탐색 DFS를 사용해서 풀어야 한다
깊이 우선 탐색으로 써야하고 binary search tree인것도 알겠는데 그래프 구현을 못했다ㅎ 문제를 이해해도 못풀고 이해 못해도 못품

재귀함수를 이용한 풀이

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

1. 초기 값 (0,0)
2. x가 numbers의 길이가 될 때 까지 반복
   x + 1, value + numbers[x] 과 x + 1, value - numbers[x]를 반복
3. x가 numbers.length이고 value가 타겟과 같다면 answer에 +1을 해줘 개수를 센다

재귀함수 공부를 해야겠다 재귀가 보면 이해는 가는데 짤 때 못짜겠음 ㅠ

binary search tree & dfs를 사용한 풀이

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    let newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return this;
    } else {
      let current = this.root;
      function traverse(node) {
        if (node.left) traverse(node.left);
        if (node.right) traverse(node.right);
        if (node.left === null) {
          let leftNode = new Node(-value);
          let rightNode = new Node(value);
          node.left = leftNode;
          node.right = rightNode;
        }
      }
      traverse(current);
      return this;
    }
  }
  DFSPreOrder(target) {
    let count = 0;
    let data = 0;
    let current = this.root;
    function traverse(node) {
      data = data + node.value;
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      if (node.left === null) {
        if (data === target) {
          count++;
        }
      }
      data = data - node.value;
    }
    traverse(current);
    return count;
  }
}

function solution(numbers, target) {
  var answer = 0;
  var answer = 0;

  let root = new BinarySearchTree();
  root.insert(0);
  numbers.forEach(function (val) {
    root.insert(val);
  });

  answer = root.DFSPreOrder(target);
  return answer;
}

binary search tree 공부하기