정수 n이 주어졌을 때, 1부터 n까지의 모든 숫자를 사전식(lexicographic) 순서로 반환하는 것이 이 글의 목표입니다. 예를 들어 n = 13이 주어지면 출력은 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]가 됩니다. 사전식 순서란 숫자를 문자열처럼 비교하여 정렬하는 방식이므로, 일반적인 수치 오름차순 정렬과는 전혀 다른 결과가 나옵니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
크기가 n인 배열 ret을 정의합니다.
curr := 1로 초기화합니다.
i를 0부터 n-1까지 반복합니다.
ret[i] := curr
만약 curr * 10 <= n이면, curr := curr * 10으로 갱신합니다. (숫자 뒤에 한 자리를 추가)
그렇지 않다면 다음을 수행합니다.
만약 curr >= n이면, curr := curr / 10
curr을 1 증가시킵니다.
curr이 10으로 나누어 떨어지는 동안 curr := curr / 10을 반복합니다. (뒤따르는 0 제거)
배열 ret을 반환합니다.
동작 원리 이해하기
이 알고리즘은 개념적으로 1부터 9까지 각 숫자를 루트로 하는 가상의 트라이(trie)를 깊이 우선 탐색(DFS)하는 과정과 동일합니다. curr * 10 <= n 조건은 현재 숫자 뒤에 0을 붙였을 때 여전히 n 이하인지 확인하는 단계이며, 더 이상 내려갈 수 없을 때는 다음 형제 노드(curr + 1)로 이동한 뒤 끝자리의 0을 제거하며 올바른 위치로 되돌아옵니다. 이렇게 하면 정렬 없이 O(n) 시간 안에 사전식 순서 배열을 만들 수 있습니다.
예제 코드(C++)
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector <int> ret(n);
int curr = 1;
for(int i = 0; i < n; i++){
ret[i] = curr;
if(curr * 10 <= n){
curr*= 10;
} else {
if(curr>= n)curr /= 10;
curr += 1;
while(curr % 10 == 0)curr/=10;
}
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.lexicalOrder(20));
}
입력
20
출력
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 3, 4, 5, 6, 7, 8, 9]
복잡도 분석
각 숫자를 한 번씩만 처리하므로 시간 복잡도는 O(n)이며, 결과를 저장하는 배열 때문에 공간 복잡도 역시 O(n)입니다. 정렬 기반 접근(O(n log n))보다 효율적이므로, n이 큰 경우에도 안정적으로 동작합니다.