57.md

타겟 넘버

나는 왜 for문을 넣었을까?

Try1

INPUT이 [1, 1, 1, 1, 1] 인 경우에 대한 모식도를 그린 것

나는 위 모식도와 같은 상황을 설계하였다. 즉 숫자와 숫자 사이에 +/-를 선택하는 경우를 반복하는 것을 구현해보자 라는 의도였다. 그래서 아래와 같은 코드를 작성하였다.

function solution(numbers, target) {
  let count = 0;
  let sum = 0;
  const checked = [];

  const dfs = (l, sum, str) => {
    if (l === numbers.length) {
      console.log(str); // 체크용
      if (sum === target) count++;
      return;
    }

    for (let i = 0; i < numbers.length; i++) {
      if (!checked[i]) {
        checked[i] = 1;
        dfs(sum + numbers[i], l + 1, str + `+${numbers[i]}`);
        dfs(sum - numbers[i], l + 1, str + `-${numbers[i]}`);
        checked[i] = 0;
      }
    }
  };

  dfs(0, 0, '');

  return count;
}

그런데 위 결과가 내가 생각하는 것보다 훨씬 많은 중복된 값이 나오는 것이였다. 여기서 잘못된 점은 바로 for문이였다.(이 부분을 가지고 많은 시간을 고민하였다.) for문을 도는 이유는 가지수(모식도에서 보면 노드에서 뻗어나가는 가지수를 말함)의 반복됨을 for문으로 대체하는 것이다. 그런데 나는 이미 그 가지수를 재귀 2번을 사용함으로서 이를 해결했다. 그런데 거기서 for문을 또 순회하게 되면 반복에 반복, 중복에 중복이 되는 결과를 초래한다.

결국 위 코드는 for문만 빼면 거의 완성된 코드였던 것이다. 하지만 문제는 내가 그 부분을 빠르게 캐치하지 못했고, 이해하는데 오래걸렸다는 것! 🙏🏻

Try2

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

  const dfs = (sum, l) => {
    if (l === numbers.length) {
      if (sum === target) count++;
      return;
    }

    dfs(sum + numbers[l], l + 1);
    dfs(sum - numbers[l], l + 1);
  };

  dfs(0, 0);

  return count;
}

이렇게 코드가 변경되었다.

결론

며칠간 DFS/BFS에 대한 기본(?) 문제들을 통해서 해당 유형에 익숙해지려고 노력했었다. 이 문제도 그렇게 어려운 문제는 아니였다. 그럼에도 아직 뭔가 서툴고 사고의 과정/논리의 과정에서 미숙함이 많다고 느낀다. 그리고 아직 나의 모식도와 나의 사고의 싱크가 맞지 않는 것 같기도 하다. 좀 더 그려보고 생각해보는 시간이 필요해보인다. 🔥