[LeetCode] Numbers With Same Consecutive Differences

문제링크

Numbers With Same Consecutive Differences - LeetCode

 

현재 자리수와 이전 자리수, 이후 자리수를 뺀 절대값이 k를  만족하는 모든 수를 구하는 문제이다.
n은 반환 숫자의 자리수, k는 반환 숫자의 인접한 자리수끼리의 차의 절대값을 의미한다.
조건 : 0으로 시작하는 수는 올 수 없다.
2 <= n <= 9, 0 <= k <= 9

접근 방법

n = 3, k = 4일때 하나의 예를 들어보면

	1
	5
1		9

이처럼 1 => 15 => 151 or 159 라는 방식으로 진행할 수 있다. (DFS 문제)

즉, 현재의 값에 k를 더하거나 뺀 값이 0 ~ 9 사이면 추가하는 방식으로 진행할 수 있다.

 

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
  const output = [];

  const DFS = (n, num) => {
    if (n === 0) return output.push(num);

    const lastDigit = num % 10;

    const nextDigits = new Set([lastDigit - k, lastDigit + k]);

    for (const nextDigit of nextDigits) {
      if (0 <= nextDigit && nextDigit < 10) {
        const newNum = num * 10 + nextDigit;
        DFS(n - 1, newNum);
      }
    }
  };

  for (let num = 1; num < 10; num++) {
    DFS(n - 1, num);
  }

  return output;
};