위 글은 2020년 03월 21일에 발행되었습니다. 비슷한 주제의 포스팅을 연속적으로 나열하고자 위해 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 함수를 작성해주세요.
입출력 예
| numbers | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
첫번째 시도 : 더할 아이템의 인덱스만 별도의 배열에 넣자
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);
맞았다. 연산을 배열의 끝에 이를때까지 미룰 필요가 없었다.
마무리
왜 프로그래머스 상에 포함/배제 재귀 문제가 DFS/BFS 분류에 넣어졌는지 의문이 든다.
이번 문제는 손 코딩으로 어떻게 풀지 생각을 먼저 한 뒤에, IDE를 거쳐보지 않고 프로그래머스 테스트 환경으로 바로 옮겨본 첫 시도였다.
단순한 포함/배제 원리를 따른 재귀 문제라 쉽게 풀 수 있었지만, 다른 문제도 이런 식으로 쉽게 풀 수 있게 끔 손 코딩을 더 수련해볼 생각이다.