[leetcode] 386. Lexicographical Numbers 파이썬 코드

https://leetcode.com/problems/lexicographical-numbers

 

lexicographical order로 정렬하라는 문제다. 

예시를 보면 딱 알 수 있다.

n = 13 이면, 정렬된 output은 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] 이다.

 

DFS로 풀 수 있다. 

 

이 솔루션의 time complexity는 노드를 한 번씩 방문하니까 O(n)이다. 

class Solution(object):
    def lexicalOrder(self, n):
        res = []

        def dfs(curr):
            # base case
            if curr > n:
                return
            res.append(curr)

            for i in range(10):
                dfs(curr * 10 + i)

        for i in range(1, 10): # 가장 맨 앞의 숫자
            dfs(i)
            
        return res

 

 

 

참고

https://youtu.be/QihtII-FvLo?si=GKTQiy0SI_bcI5co