[Leetcode] 738. Monotone Increasing Digits

https://leetcode.com/problems/monotone-increasing-digits/description/

어떤 숫자보다 작거나 같은 수 중에서 숫자의 배열이 오름차순인 가장 큰 수 찾기 문제이다.

처음에는 0부터 시작할 까 했으나 수의 범위가 10억까지라서 거꾸로 내려가보기로 했다.

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        tmp = n
        while not isAsc(tmp):
            tmp -= 1
        return tmp
        
    


def isAsc(number):
    s = list(map(int, str(number)))

    chk = True

    for i in range(1, len(s)):
        if s[i-1] > s[i]:
            chk = False
    
    return chk 

n부터 거꾸로 내려가면서 isAsc라는 함수로 돌아가는데 isAsc는 숫자를 문자열로 바꿔서 오름차순인지 판별하는 함수다.
하지만 테스트케이스 중 2억정도 되는 숫자에서 시간초과가 났다.

문제 해결을 위해 다른 풀이를 찾았다.

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)
        l = len(n)

        for i in range(l-1):
            if n[i] > n[i+1]:
                break
        else:
            return int(n)


        while i>0 and n[i-1] == n[i]: i -= 1

        print(i)

        return int(str(int(n[:i+1])-1) + '9' *(l-i-1))

이거는 숫자에 대해서 숫자가 작아지는 자릿수를 찾은 다음 그 자릿수 기준으로 오름차순을 만족하는 곳을 찾는다. 그리고 거기서 1을 뺀 다음 나머지 자리는 9로 채워줬다.
즉 12443이면 1244까지 갔다가 오름차순을 만족하는 곳 124까지 남기고 1을 빼서 123을 만든 다음 12399로 답을 구했다.
문제에서 규칙을 찾는게 좀 어려운 것 같다. 더 연습이 필요하다.