프로그래머스: 43165, 타겟 넘버

문제 설명

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 함수를 작성해주세요.

입출력 예
numberstargetreturn
[1, 1, 1, 1, 1]35

첫번째 시도 : 더할 아이템의 인덱스만 별도의 배열에 넣자

go([...array, index], index + 1, numbers, target) +
  go(array, index + 1, numbers, target);

포함/배제의 원리에 따라 재귀로 더할 아이템의 인덱스를 별도의 배열 array에 넣었다. 배열의 끝에 다다르면 array 값 각각을 numbers 배열에 색인시키며 더한다. 그리고 [0 ~ numbers.lenght-1]array 의 차집합을 구해 numbers 배열에 색인시키며 뺀다.

const difference = (array: number[], n: number) =>
  [...new Array(n).keys()].filter(x => !array.includes(x));

if (index == numbers.length) {
  let cnt = 0;
  for (const i in array) cnt += numbers[i];
  for (const i in difference(array, numbers.length)) cnt -= numbers[i];
  if (cnt == target) return 1;
  return 0;
}

입출력 예로 나온 값은 맞았지만 숨은 테스트 케이스가 틀렸다.

두번째 시도 : 즉시 더하기/빼기를 작업을 하자

go(index + 1, cnt + numbers[index], numbers, target) +
  go(index + 1, cnt - numbers[index], numbers, target);

맞았다. 연산을 배열의 끝에 이를때까지 미룰 필요가 없었다.

소스코드

고쳐본 소스코드 DIFF 결과

마무리

왜 프로그래머스 상에 포함/배제 재귀 문제가 DFS/BFS 분류에 넣어졌는지 의문이 든다.

이번 문제는 손 코딩으로 어떻게 풀지 생각을 먼저 한 뒤에, IDE를 거쳐보지 않고 프로그래머스 테스트 환경으로 바로 옮겨본 첫 시도였다.

단순한 포함/배제 원리를 따른 재귀 문제라 쉽게 풀 수 있었지만, 다른 문제도 이런 식으로 쉽게 풀 수 있게 끔 손 코딩을 더 수련해볼 생각이다.