백준 1038 감소하는 수

"감소하는 수" 를 만드는 함수를 작성했는데 풀다보니 함수를 여러개 만들었고 코드가 길어졌다..
시간은 백준사이트 상 48ms 로 빠른거 같은데 코드가 이렇게 까지 길 필요는 없을 것이다..!

📜 문제 바로 가기 : 감소하는 수

제출코드

import sys
input = sys.stdin.readline

def find_number(x):
    if x < 10:
        return x
    
    n = 10
    number = 10
    while n != x and number != -1:
        n += 1
        number = next_number(number)

    return number

def isRight(x): # x가 감소하는 수 인가?
    s_num = str(x)
    for i in range(len(s_num)-1):
        if s_num[i] <= s_num[i+1]:
            return len(s_num) - i -1# len(s_num) - i -1 번째 자리수에서 규칙이 깨졌다. 
        
    return 0 # 감소하는 수이다!


def next_number(n):
    if isFinal(n): # True 면 자리수 올림
        return next_count(n)
    
    n += 1 # 일단 1 더해본다.
    flag = isRight(n) # 검증
    
    if flag == 0: # 감소하는 수 이면 그대로 리턴
        return n
    
    # 감소하는 수가 아니면
    return remake(n, flag)


def remake(n, k): # 숫자 n 이 k자리수에서 규칙이 깨졌다.
    # 984421 # 3자리에서 규칙이 깨졌다.
    # 985210 를 리턴한다.
    # k+1 자리수의 숫자를 하나 올리고
    
    s_num_list = list(str(n))
    up_pos = len(s_num_list) - k -1
    tmp = int(s_num_list[up_pos])

    if up_pos == 0 and tmp == 9:
        return next_count(n)
    
    s_num_list[up_pos] = str(tmp + 1) # k+1 자리수 숫자 up

    new_num = ""
    for i in s_num_list[:up_pos+1]:
        new_num += i

    tmp = ""
    for i in range(len(s_num_list) - len(new_num)):
        tmp = str(i) + tmp
    new_num += tmp


    new_num = int(new_num)

    flag = isRight(new_num) # 검증
    
    if flag == 0:
        return new_num

    return remake(new_num, flag)


def isFinal(n): # 숫자 n 이 그 자리수에서 마지막 감소하는 수인가?
    # 즉 그 자리수에서 가장 큰 감소하는 수인가
    l = len(str(n)) # 자리수
    k = ""
    for i in range(l):
        k += str(9-i)
    
    final_Number = int(k)
    if final_Number == n:
        return True
    return False

def next_count(n): # 자리수 증가
    if n == 9876543210:
        return -1 # 9876543210 보다 큰 감소하는 수는 없다.
    
    l = len(str(n)) + 1

    # 7자리수의 숫자중 제일 작은 감소하는 수는
    # 6543210 이다.
    k = ""
    for i in range(l-1, -1, -1):
        k += str(i)
    
    return int(k)
    
N = int(input())

print(find_number(N))

접근방법

우선 감소하는 수는 유한하다는 점을 알아야 했다.
매 자리수가 감소해야 됨으로 가장 크게 만들 수 있는 값은 9876543210 이다.
대충 99억인데 시간은 1초 주어지므로 값을 하나 증가시고 감소하는 수를 판단 하기엔 수가 너무 크다.

하지만 수는 큰데 정작 이를 만족하는 숫자의 개수는 적다. 문제 풀때는 대충 2000개는 안될거라고 생각했고 문제로 풀고 개수를 세 보니 1023개 이다.

총 양 자체는 적기때문에 값을 하나씩 증가 시키되 가지치기를 통해 총 연산을 줄여주기로 했다.
가지치기에 사용한 로직은 크게 isFinal(), remake() 이렇게 2개이다.

isFinal(n)

숫자 n 의 자리수에서 그 수가 가장 큰 수 인지 확인한다.
예를 들어 6자리의 가장 큰 감소하는 수는 987654 이다.
이 다음 감소하는 수는 자리수가 증가되기때문에 next_count(n) 함수로 넘어간다.

remake(n, k)

숫자를 1씩 증가시키다보면 감소하는 수 규칙이 깨지기 마련이다.
그 규칙이 깨진 자리수를 파악하여 다음 감소하는 수를 제시해준다.
예를 들어 976632 는 3번째 자리수(6) 에서 규칙이 처음 깨졌다. 그러므로 remake(976632, 3) 이 실행되고 4번째 자리수에 +1 을 하고 그 뒤는 작은 수로 채운 977210 을 만든다.
그런데 977210 역시 4번째 자리수에서 규칙이 깨진다. 그럼으로 remake(977210, 4) 를 호출하여 983210 을 만든다. 이는 재귀를 통해 구현하였다.