386. Lexicographical Numbers

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:14:11

 

---

 

문제 설명

 

 

정수 n을 입력으로 받았을 때, [1, n] 범위의 정수를 사전식 순서대로 정렬하여 반환하라.

 

이 때, O(n)시간복잡도와 O(1) 추가 공간복잡도 알고리즘을 사용해야만 한다.

---

 

풀이

 

사전식 순서 = DFS.

 

사전식 순서의 규칙을 떠올려보자.

• 한 숫자가 다른 숫자의 진부분집합이면, 그 숫자가 앞에 와야 한다 (예 : 111 -> 1111 -> 1112)
• 그렇지 않다면..
  • 처음 자리부터 두 숫자의 교집합을 구하고 (예 : 111452,)
  • 교집합이 아닌 자리수부터 둘을 비교하여, 더 작은 숫자가 앞에 오도록 한다. (예 : 111324 -> 111452)

..이런 규칙으로 정의할 수 있고, 이 규칙을 직감적으로 이해하면(?) 바로 DFS를 적용할 수 있다.

 

1. 어떤 숫자를 방문한다. (전제 : 그 숫자는 n보다 작다)
2. 그 숫자를 리스트에 저장한다.
3. 그 숫자 뒤에 0을 붙여 본다.
   • 새롭게 만들어진 숫자가 n보다 작다면, 그 숫자를 가지고 1로 방문한다. 방문 결과를 리스트에 저장한다.
   • 그렇지 않다면, 그 숫자는 방문할 필요가 없다(n보다 큰 숫자이므로). 다음으로 넘어간다.
4. 3과 같은 방식으로 1~9까지 숫자를 붙여 본다.
5. 리스트를 반환한다.

 

DFS를 사용하면, n보다 작은 수들을 한 번씩만 방문하면 되므로 시간복잡도는 O(n)이 된다. 공간복잡도 역시 O(1) (결과 저장값 이외의 별도의 변수를 사용하지 않음) 이 된다. (재귀식으로 방문했을 때 한정. 비재귀 - 즉 스택 등을 이용하면 공간복잡도는 O(k)가 될 것이다(k는 n의 자릿수))

 

풀이 코드

class Solution:
    def search(self, n: int, cur: int) -> List[int]:
        result = [cur]
        for i in range(10) :
            tmp = cur*10 + i
            if tmp > n :
                return result
            result += self.search(n, tmp)
        return result
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        for i in range(1, min(n, 9)+1) :
            result += self.search(n, i)
        return result

풀이 완료!