문제 소개
숫자 n이 주어졌을 때, 사전식(lexicographic) 순서로 정렬된 처음 n개의 숫자를 찾아야 합니다. 사전식 순서란 숫자를 문자열처럼 취급하여 사전에서 단어를 정렬하듯이 순서를 매기는 방식을 의미합니다.
예를 들어 입력이 n = 15라면 출력은 다음과 같습니다.
[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]
일반적인 오름차순(1, 2, 3, …)과 달리 사전식 순서에서는 10이 2보다 앞에 위치합니다. 숫자를 문자열로 비교할 때 첫 자리 '1'이 '2'보다 작기 때문입니다.
알고리즘 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- count를 1로 초기화합니다.
- ans를 count 하나만 포함하는 리스트로 초기화합니다.
- ans의 크기가 n보다 작은 동안 아래 과정을 반복합니다.
- count := count × 10
- count가 n보다 큰 동안 아래 과정을 반복합니다.
- count := count ÷ 10의 몫
- count := count + 1
- count를 10으로 나눈 나머지가 0인 동안 count := count ÷ 10의 몫을 반복합니다.
- ans의 끝에 count를 추가합니다.
- 최종적으로 ans를 반환합니다.
핵심 아이디어는 다음 숫자를 찾을 때 먼저 10을 곱해 한 자릿수를 늘린 뒤, n의 범위를 벗어나면 자릿수를 줄이고 1을 더하는 방식으로 사전식 순서상 다음 숫자를 차례대로 구하는 것입니다.
구현 예제 코드
class Solution:
def solve(self, n):
count = 1
ans = [count]
while len(ans) < n:
count *= 10
while count > n:
count = count // 10
count += 1
while count % 10 == 0:
count = count // 10
ans.append(count)
return ans
ob = Solution()
n = 15
print(ob.solve(n))
입력
15
출력
[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9]
복잡도 분석
시간 복잡도는 O(n)입니다. 사전식 순서상 각 숫자를 정확히 한 번씩만 방문하면 되기 때문입니다. 공간 복잡도 역시 결과를 저장하는 리스트를 위해 O(n)이 필요합니다.