C++의 모노톤 증가 자릿수

음이 아닌 정수 N이 있다고 가정하면 단조 증가 자릿수로 N보다 작거나 같은 가장 큰 숫자를 찾아야 합니다. 인접한 숫자의 각 쌍' x와 y가 x <=y를 충족하는 경우에만 정수가 단조 증가 숫자를 갖는다는 것을 알고 있습니다. 따라서 입력이 332와 같으면 결과는 299가 됩니다.

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

• s :=N을 문자열로, i :=1, n :=s의 크기
• 동안 i =s[i – 1]
  • i를 1 증가
• 내가 이면
• i> 0 및 s[i – 1]> s[i]인 동안
  • i를 1 감소
  • s[i] 1 감소

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int monotoneIncreasingDigits(int N) {
      string s = to_string(N);
      int i = 1;
      int n = s.size();
      while(i < n && s[i] >= s[i - 1]) i++;
      if( i < n)
      while(i > 0 && s[i - 1] > s[i]){
         i--;
         s[i]--;
      }
      for(int j = i + 1; j < n; j++)s[j] = '9';
      return stoi(s);
   }
};
main(){
   Solution ob;
   cout << (ob.monotoneIncreasingDigits(332));
}

입력

332

출력

299