[LeetCode] 386. Lexicographical Numbers

https://leetcode.com/problems/lexicographical-numbers/description/?envType=daily-question&envId=2024-09-21

leetcode - Lexicographical Numbers

문제 유형 : 수학, 구현, dfs, 재귀

문제 난이도 : Medium

 

문제

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space. 

 

정수 n이 주어진다. [1, n]의 모든 숫자들을 사전순으로 정렬하여 반환하시오.

당신은 선형 시간에 상수 추가 공간만을 사용해야 합니다.

 

풀이

우선, 배열의 시작은 반드시 1이 된다. 그러고 다음 숫자를 구해서 넣으면 된다.

그리고 다음 숫자를 구하는 것은, dfs를 생각하면 편하다.

만약 10을 곱한 값이 n보다 작다면, 그 숫자가 사전적으로 더 앞에 위치한다.

  그러므로, 다음 숫자는 10을 곱한 값이 된다.

만약 n을 초과하거나 같다면, 수를 줄여야 한다. 현재 숫자에서 10을 나눈다.

그 외의 경우는 현재 수에 1을 누적한다. 만약 0으로 끝나는 경우에는, 10을 계속 나눠준다.

(예를 들어, 19 다음은 20이 되는데, 그 앞에 2가 먼저 나와야 한다.)

 

 

코드

C++

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> result;
        int current = 1;

        for (int i = 0; i < n; ++i) {
            result.push_back(current);
            current = getNextNumber(current, n);
        }


        return result;
    }

private:
    int getNextNumber(int current, int n) {
        if (current * 10 <= n) {
            return current * 10;
        }

        if (current >= n) {
            current /= 10;
        }
        
        current += 1;
        while (current % 10 == 0) {
            current /= 10;
        }

        return current;
    }
};