Monotone Increasing Digits

738. Monotone Increasing Digits

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        int result = 0;
        while (n) {
            int i = n % 10;
            n /= 10;
            if (n) {
                int nx = n % 10;
                if (i < nx || (nx == 0 && i == 0)) {
                    --n;
                    i = 9;
                    int l = 0;
                    while (result) {
                        ++l;
                        result /= 10;
                    }
                    while (l) {
                        result *= 10;
                        result += 9;
                        --l;
                    }
                }
            }
            result *= 10;
            result += i;
        }
        n = 0;
        while (result) {
            n *= 10;
            n += result % 10;
            result /= 10;
        }
        return n;
    }
};

1의 자리 숫자를 기억해 두고 주어진 값을 10으로 나눈다. 주어진 수의 1의자리수 부터 한단위 큰 자리수의 숫자보다 작거나 둘다 0 이면 숫자를 9로 바꾸고 현재까지 구한 결과의 모든 자리수의 값을 9로 바꾼다.

• 0 보다 작은 숫자가 없으므로, 둘다 0 이라면 더 앞자리 어딘가에서 숫자를 감소 시켜야만 한다.
• 한 자리수 단위로 보았을때, 10000 같은 수에서 1을 빼면 앞의 자리수 까지 1 감소 해준게 전파되는것으로 볼 수 있다.
• 높은자리수에서 1이 감소했으므로 더 낮은 자리수에서 가장 큰 값은 모두 9가 되어야 한다.

결과 값에 10 곱하고 1의자리 수에 구한 값을 더한다.
뒤의 숫자부터 채워넣었으므로 reverse 해준다.

Time: O(log(n))

• n 의 자리수만큼 루프를 돌게 되므로 log(n)

Space: O(1)

• 입력, 출력 외에 공간 필요 없음.