1. 타겟 넘버

이 문제는 숫자가 담긴 배열이 주어지고 그 숫자를 더하거나 빼서 타겟 넘버와 일치하면 되는 것이다. 예를 들어, [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

이때 떠오르는 것은 부분 집합이다. check Array를 통해 더하고 빼는 원소를 경우를 모두 구한다음 계산하는 것이다.

2. 접근 방법

• pseudo code
  • check 배열을 만들고 그 배열에 따라서 numbers안에서의 원소를 더하고 뺀다.
    • check는 0,1로 이루어져있고 1일때 더하고 0일때 뺀다
  • dfs를 만들고 dfs에 pass되는 숫자가 numbers의 길이와 같을때 계산한다.

function mySolution(numbers, target) {
  let answer = 0;
  let ch = [];
  let finalSum = 0;

  function dfs(level) {
    if (level === numbers.length) {
      console.log(ch);
      for (let i = 0; i < ch.length; i++) {
        if (ch[i] === 0) {
          finalSum -= numbers[i];
        } else finalSum += numbers[i];
      }
      console.log(finalSum);
      if (finalSum === target) answer++;
      finalSum = 0;
    } else {
      ch[level] = 1;
      dfs(level + 1);
      ch[level] = 0;
      dfs(level + 1);
    }
  }

  dfs(0);

  return answer;
}

요렇게 하고 정답을 맞추었다. 배운것을 써먹다니 감게무량하다..ㅠㅠ 그럼 ch와 finalSum을 출력해보자

[1, 1, 1, 1, 1]
=> 5(1+1+1+1+1)

[1, 1, 1, 1, 0]
=> 3(1+1+1+1-1)

[1, 1, 1, 0, 1]
=> 3

[1, 1, 1, 0, 0]
=> 2

[1, 1, 0, 1, 1]
=> 3

[1, 1, 0, 1, 0]
=> 2
.
.
.

요런식으로 진행이 된다. 그래서 3이되는게 5개 있어서 정답은 5로 출력. 여기서 항상 해야할거! 남들의 코드를 보고 배우는 것이다.

function otherSolution(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;
}

아하!! value의 값을 누적해서 넘겨준다... +와 -의 값을 말이다. for문이 없어서 빠르고 check배열이 없어서 메모리사용도 적다. 고로 이 코드가 더 효율적이다. 배웠다 진짜 매일 배우고 써먹고 해서 정말 기부니가 좋다.

3. 배운점

1. 잘 안풀리면 바로바로 디버깅해서 문제를 발견하자. 그냥 아무생각없이 붙잡고 있으면 잡생각만나고 졸리고 늘어진다. 티키타가가 잘 되어야 한다. 바로바로 찾고 적용해서 집중력이 끊어지지 않게 해보자

2. 아예 상자밖에서 새롭게 써내려가는 방법이 필요하다. 내가 알고 있던 check배열을 일단은 내려놓고 순수하게 접근할 필요도 있을것 같다.