๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ“š Study Note/LeetCode

967. Numbers With Same Consecutive Differences

by Jellll_y 2022. 11. 26.

967. Numbers With Same Consecutive Differences

Medium


Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

 

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.

 

Constraints:

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

0 ~ 9๊นŒ์ง€์˜ ์ˆซ์ž๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ธธ์ด๊ฐ€ n์ด๊ณ , ์—ฐ์†๋˜๋Š” ์ˆซ์ž์˜ ์ฐจ์ด๊ฐ€ k์ธ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

์ด ๋ฌธ์ œ๋Š” n <= 15์ด๊ณ  ์ „์ฒด๋ฅผ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ๊ฐ€์ง€์น˜๊ธฐ๋ฅผ ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฑํŠธ๋ž˜ํ‚น์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋‹ค.

 

๋ฐฑํŠธ๋ž˜ํ‚น์˜ ์˜์‚ฌ์ฝ”๋“œ๋Š” 

1. path์˜ ๊ธธ์ด๊ฐ€ 1 ์ด์ƒ์ผ ๋•Œ( ๋‘ ๊ฐœ๋ฅผ ๋น„๊ต ๊ฐ€๋Šฅ) ์—ฐ์†๋˜๋Š” ๋‘ ์ˆซ์ž์˜ ์ฐจ์ด๋ฅผ ๊ตฌํ•œ๋‹ค, ์ด๋•Œ k๊ฐ€ ์•„๋‹ˆ๋ผ๋ฉด return

2. path ์˜ ๊ธธ์ด๊ฐ€ n์ผ ๊ฒฝ์šฐ ans์— ํ‘ธ์‹œํ•œ๋‹ค.

3. for๋ฌธ์„ ์ˆœํšŒํ•œ๋‹ค.

4. 0์ด ์•ž์— ์˜ฌ ์ˆ˜ ์—†์œผ๋ฏ€๋กœ (01 ๋ถˆ๊ฐ€๋Šฅ) path์˜ ๊ธธ์ด๊ฐ€ 0์ด๊ณ  i ๊ฐ€ 0์ผ ๋•Œ continue

5. path์— ํ•ด๋‹น ์ˆซ์ž ํ‘ธ์‹œํ›„ ์žฌ๊ท€๋ฅผ ํ†ตํ•ด ๋ฐ˜๋ณต 

 

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {
    const backtrack = (path) => {
        if(path.length > 1 && Math.abs(path.at(-2) - path.at(-1)) !== k) return 
        if(path.length === n){
            ans.push(path.join(''))
            return
        }
        for(let i=0; i<=9; i++){
            if(path.length === 0 && i === 0) continue
            path.push(i)
            backtrack(path)
            path.pop()
        }
    }
    
    const ans = [] 
    backtrack([])
    
    return ans
};

'๐Ÿ“š Study Note > LeetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

346. Moving Average from Data Stream  (0) 2022.12.26
2225. Find Players With Zero or One Losses  (0) 2022.11.28
49. Group Anagrams  (0) 2022.11.26
216. Combination Sum III  (0) 2022.11.24
39. Combination Sum  (0) 2022.11.24