타겟 넘버

Link

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

Deadline

Oct 19, 2021

Status

Archived

Type

BFS

DFS

📄문제

✏️풀이

은찬


function dfs(current, count, numbers, target){
    if(count === numbers.length){
        if(current === target){
            return 1;
        }
        return 0;
    }
    let answer = 0;
    
    answer += dfs(current + numbers[count], count + 1, numbers, target);
    answer += dfs(current - numbers[count], count + 1, numbers, target);
    
    return answer;
}

function solution(numbers, target) {
    return dfs(0, 0, numbers, target);
}

재영 띱~


class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}

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

  const queue = new Queue();
  queue.enqueue([0, numbers]);

  while (queue.size()) {
    const [nowSum, nowArr] = queue.dequeue();
    if (!nowArr.length) {
      if (nowSum === target) {
        answer += 1;
      }
      continue;
    }
    const nextArr = [...nowArr];
    const nowShifted = nextArr.shift();
    queue.enqueue([nowSum + nowShifted, nextArr]);
    queue.enqueue([nowSum - nowShifted, nextArr]);
  }

  return answer;
}

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

효성


function solution(numbers, target) {
    let count = 0;
    
    function dfs(depth, sum) {
        if(depth === numbers.length){
            if(sum === target){
                count++;
            }
            return;
        }
        dfs(depth+1, sum + numbers[depth]);
        dfs(depth+1, sum - numbers[depth]);
    }
    dfs(0, 0);
    return count;
}