감소하는 수 - PYTHON

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

문제 해결

처음 문제를 접했을 때는 단순하게 10에서 ( 첫 감소수 ) 부터 1씩 더하며 감소수 이면 카운트 +1 로 카운트 == N 이면 수를 리턴하는 단순하게 구현 하였으나 아니나 다를까 시간초과....🥲

그렇다면 인간의 경우 어떻게 14번째를 알 수 있을까?

1. 10에서 시작 ( 1자리는 모두 감소 수기 때문에 ).
2. 그런데 1보다 작은 수가 0 뿐 => +1
3. 20으로 넘어감, 2보다 작은 수는 1,0 => +2
   ..
4. 500이라면, 5보다 작은수 4,3,2,1,0 => 각각 [3,2,1,0], [2,1,0] , [1,0] , [0]...

그러나 N 자리 수에 따라 중간 값이나 그런 것을 만들기 쉽지 않기에,

1. 0부터 수를 증가시키면서 N번째 감소하는 수를 찾을 때까지 2, 3번 과정을 반복합니다.
2. 현재 수가 감소하는 수이면 num + 1을 수행합니다.
3. 현재 수가 감소하는 수가 아니면 감소하도록 수정합니다.
4. N번째 감소하는 수를 찾으면 출력합니다.

코드

def decrease(N):
    cnt = 0
    num = 1
    while True:
        str_num = str(num)
        flg = True

        if len(str_num) == 1:
            pass
        else:
            for i in range (1,len(str_num)):
                if int(str_num[i]) < int(str_num[i-1]): # 감소하는 수인가?
                    continue
                else: # 아니면 감소하지 않는 위치가 감소하도록 수정합니다.
                    start = str_num[:i-1]
                    mid = str(int(str_num[i-1]) + 1)
                    end = '0' + str_num[i+1:]
                    num = int(start+mid+end)
                    flg = False
                    print("start: "+start+" mid: "+mid+" end: "+ end)
                    break
                    
        
        if flg: # 감소하는 수이면 현재 수 + 1 살펴보고 , 갯수에 추가
            cnt +=1
            if cnt == N: # 만약 원하는 갯수에 만족하면 num 리턴.
                return num
            num += 1 # 부족하면 다음 넘버 체크


N = int(input())
if N == 0 : 
    print(0)
elif N >= 1023:
    print(-1)
else:
    print(decrease(N))

N이 1023일때 정수의 최대값이 넘어가기 때문에 -1 을 해줍니다. 주어진 예시 18로 동작을 한번 시켜보도록 하죠.

먼저 str_num 의 길이는 2자리가 됩니다. 그 중 1자리 수는 모두 감소하는 수입니다. 그렇기 때문에 아래 else 부분에는 len()은 최소 2부터 시작하게 됩니다.

num = 10) i = 1, 그리고 str_num[1] < str_num[0] = 감소하는 수인가? YES 👉 num = 11
num = 11) i = 1, ... 감소? NO 👉 start= str_num[:0] = '\0' , mid = int(str_num[0]) + 1 = 2 , end = '0' + str_num[2:] = '0'+ '\n' = '0' 👉 num = 20 ,21
...
...
num = 101) i = 1, ...감소? YES
i = 2, ...감소? NO 👉 start = str_num[:1] = '1' , mid = int(str_num[1]) + 1 = 1 , end = '0' + str_num[3:] = '0'+ '' = '0' 👉 num = 110

num = 110) i = 1, ...감소? NO 👉 start = str_num[:0] = '\0' , mid = int(str_num[0]) + 1 = 2 , end = '0' + str_num[2:] = '0'+ '0' = '00' 👉 num = 200
....

이렇게 인덱스 슬라이스로 다음, 다음으로 넘어가며 판별하고 맞으면 다음 숫자를 검사해보는 형식으로 진행한다.