[리트코드] 967. Numbers With Same Consecutive Differences / Javascript

문제주소 : https://leetcode.com/problems/numbers-with-same-consecutive-differences/

Numbers With Same Consecutive Differences - LeetCode

---

<문제 설명>

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

 

Example 1:

Input: n = 3, k = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: n = 2, k = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Example 3:

Input: n = 2, k = 0 Output: [11,22,33,44,55,66,77,88,99]

Example 4:

Input: n = 2, k = 2 Output: [13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

 

Constraints:

• 2 <= n <= 9
• 0 <= k <= 9

 

<풀이법>

▒ 한줄 개념: dfs ▒ 

dfs, bfs를 사용해 푸는 문제인데, 순열 문제와 비슷한 느낌입니다.

저는 dfs를 사용했고, 풀이방식은 다음과 같습니다.

 

1. 반복문을 통해 하나의 i값으로 된 string을 만들어주고, 이를 사용해 dfs(i)를 실행해줍니다.

  - i = 1, dfs(1)

  - i = 2, dfs(2)

  - i = 3, dfs(3)

2. dfs를 통해 해당 string의 last 값(마지막 인덱스 값)을 가져옵니다.

  - '1' 의 경우 last = 1

  - '13' 의 경우 last = 3

  - '1452' 의 경우 last = 2

3. last - k >= 0 의 경우, last-k를 현재 string에 추가하여 dfs를 재귀 실행해줍니다.

  - k = 3일 때,

  - '4'의 경우 last = 4, dfs(41)

  - '36'의 경우 last = 6, dfs(363)

  - '74'의 경우 last = 4, dfs(741)

4. last + k < 10의 경우, last+k를 현재 string에 추가하여 dfs를 재귀 실행해줍니다.

  - k = 3일 때,

  - '4'의 경우 last = 4, dfs(47)

  - '36'의 경우 last = 6, dfs(369)

  - '74'의 경우 last = 4, dfs(747)

5. 재귀를 반복하다가 만약 cur(현재 string)의 길이가 n이고, cur이 answer에 속해있지 않으면, 추가해줍니다.

 

<코드(Javascript)>

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {
    const answer = [];
    
    const dfs = cur => {
        if(cur.length === n){
            if(answer.indexOf(cur) === -1){
                answer.push(cur);
            }
        }else{
            const last = parseInt(cur[cur.length - 1]);
            if(last - k >= 0){
                dfs(cur+(last-k));
            }
            if(last + k < 10){
                dfs(cur+(last+k));
            }
        } 
    }
    
    for(let i = 1; i < 10; i++){
        dfs(String(i));
    }
    
    return answer;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest