C++의 사전식 숫자

정수 n이 있다고 가정합니다. 사전순으로 1에서 n을 반환해야 합니다. 예를 들어 13이 주어지면 출력은 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 크기가 n

  인 하나의 배열 ret를 정의합니다.

• 커 :=1

• 0 ~ n – 1 범위의 i에 대해

  • ret[i] :=커

  • curr * 10 <=n이면 curr :=curr * 10

    으로 설정합니다.

  • 그렇지 않으면

    • curr>=n이면 curr :=curr / 10

    • 통화를 1 증가

    • curr이 10으로 나누어지는 동안 curr :=curr / 10

• 리턴 렛

예시(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, ]