[python3] 967. Numbers With Same Consecutive Differences

풀이 일자: 22.09.03

난이도: [Medium]

분류: [Backtracking/BFS]

문제 내용

자릿수에 관한 정보 n과 인접한 수와의 차이를 나타내는 k를 받아서 해당 조건에 맞는 수의 List를 반환하는 문제였다.

즉 n = 3, k = 7이라 했을 때,

세자리수이고 인접한 각 자리수의 차이가 7인 수의 List를 반환해야 하므로 [181, 292, 707, 818, 929]가 이에 해당한다.

 

문제 해결 흐름

1. 받는 k에 따라 0~9까지의 수의 다음에 나올 수 있는 수를 미리 저장해두어야겠다.

→ k=0일때를 제외하고 0~9까지의 수 n 다음에 나올 수 있는 수가 (n+k, n-k)이므로 해당 정보를 딕셔너리(해쉬)로 저장하자.  k가 0일때는 n 다음에 n이 나와야 한다.

2. 이제 나올 수 있는 수를 결정해야 하는데 그래프 순회 혹은 트리 순회 느낌으로 구현하면 되지 않을까?

→ 재귀방식을 이용하여  n의 길이가 될때까지 딕셔너리 정보를 이용하여 재귀적으로 숫자를 붙여나가자.

class Solution:
    ans = list()
    numsDict = dict()
    
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        
        for i in range(10):
            element = list()
            if k == 0:
                element.append(i)
            else:
                if i - k >= 0:
                    element.append(i - k)
                if i + k < 10:
                    element.append(i + k)  
            self.numsDict[i] = element
              
        for i in range(1, 10):
            self.createNumber(i, i, 1, n)
        
        result = self.ans.copy()
        self.ans.clear()
        
        return result
    
        
    def createNumber(self, prevNum: int, consecNum: int, length: int, maxLength: int):
        if length < maxLength:
            consecNum *= 10
            for i in self.numsDict[prevNum]:
                self.createNumber(i, consecNum + i, length + 1, maxLength)
        else:
            self.ans.append(consecNum)

다른 해결 방식

1. LeetCode의 공식 Solution에서는 BFS방식과  DFS방식으로 나누었고 DFS와 BFS방식 모두 단순하게 나의 아이디어처럼 각 단계별로 숫자를 하나씩 붙여나가는 방식으로 나왔다,  User Code에서는 간단하게 풀어낸 코드가 존재했는데 간단했으나 while문 내에 list를 copy하는 과정이 존재하여 런타임이 늘어지는 결과가 나온 것을 보인다.

class Solution:
    def numsSameConsecDiff(self, n, k):
        lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        while n > 1:
            tmp = []
            for val in lst:
                rem = val % 10
                if rem + k < 10:
                    tmp.append(val * 10 + rem + k)
                if k != 0 and rem - k >= 0:
                    tmp.append(val * 10 + rem - k)
            lst = tmp
            n -= 1
        return lst

문제 링크

https://leetcode.com/problems/numbers-with-same-consecutive-differences/