문제 정의
숫자 n을 입력받아 처음 n개의 자연수를 담은 배열을 반환하는 JavaScript 함수를 작성해야 합니다. 여기서 중요한 조건은 하나뿐입니다. 배열의 숫자들은 일반적인 오름차순이 아니라 사전순(lexicographical order)으로 정렬되어야 한다는 점입니다.
사전순 정렬이란 숫자를 문자열처럼 취급해 비교하는 방식입니다. 즉, 1로 시작하는 모든 숫자(1, 10, 11, 12…)는 2, 3, 4 등으로 시작하는 어떤 숫자보다도 앞에 위치해야 합니다. 마치 사전에서 단어가 글자 순서대로 배치되는 것과 같은 원리입니다.
예시로 이해하기
n = 13인 경우를 생각해 보겠습니다. 일반적인 오름차순이라면 [1, 2, 3, …, 13]이 되지만, 사전순으로 정렬하면 다음과 같이 됩니다.
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
코드 구현
다음은 위 조건을 만족하는 JavaScript 코드입니다.
const num = 24;
const buildLexicographically = (num = 1) => {
const res = [];
const curr = num >= 9 ? 9 : num;
for (let i = 1; i <= curr; i++) {
res.push(i);
for (let j = i * 10; j <= num; j++) {
res.push(j)
if(j % 10 === 9){
break;
}
}
};
return res;
};
console.log(buildLexicographically(num));
출력 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
[
1, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 2, 20, 21, 22, 23,
24, 3, 4, 5, 6, 7, 8, 9
]
동작 원리
이 알고리즘이 사전순 배열을 만드는 과정을 단계별로 살펴보겠습니다.
- 기준 숫자 설정: 변수
curr은 n이 9 이상이면 9, 그렇지 않으면 n의 값을 가집니다. 이는 한 자리 숫자 1~9가 각각 사전순 그룹의 시작점이 되기 때문입니다. - 그룹 시작 숫자 추가: 외부 루프에서 각 기준 숫자 i를 먼저 결과 배열에 넣습니다. 예를 들어 1을 추가하면, 이후 1로 시작하는 모든 숫자가 이어지게 됩니다.
- 같은 접두어 그룹 처리: 내부 루프는 i × 10부터 시작해 n 이하의 숫자를 차례로 추가합니다. i = 1이라면 10, 11, 12… 순서로 이어집니다.
- 그룹 종료 조건:
j % 10 === 9조건은 해당 그룹의 마지막 숫자(예: 19, 29)에 도달했음을 의미합니다. 이 지점에서 내부 루프를 종료하고 다음 기준 숫자로 넘어갑니다.
결과적으로 1, 10~19, 2, 20~24, 3, 4, …, 9와 같이 사전순으로 정렬된 배열이 완성됩니다. 이 접근 방식은 각 숫자를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.