문제

https://www.acmicpc.net/problem/14791
문제요약 : 주어진 수와 가까운 등차수열인 Tidy Number를 출력해라

풀이

완전탐색으로 하면 당연하게도 시간초과가 걸린다.
1씩 줄여나갔을때 Tidy인 경우는
자기 자신이 Tidy이거나, 앞자리가 줄어들고 뒷자리가 9로 채워지는 경우밖에없으므로
10의 자리부터 각자리수를 -1 하고 나머지를 9로 채워 Tidy인지 보면된다.

divmod로 10 거듭제곱의 몫과 나머지를 구해서, 몫에 -1를 하고 뒤에 나머지의 길이만큼 9를 붙이는 식으로 풀이했다.

# 깔끔한 수인지 검사
def isTidy(n):
    return list(str(n)) == sorted(list(str(n)))

# 가장 가까운 깔끔한 수 구하기
def check(number):
    if isTidy(number):
        return number
    length = len(str(number))
    for i in range(1,length):
        a, b = divmod(number,10**i)
        target = str(a-1)+'9'*len(str(b))
        if isTidy(target):
            return int(target)

# 테스트케이스
t = int(input())
for i in range(1,t+1):
    number = int(input())
    print(f"Case #{i}:",check(number))