문제

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

입력

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

출력

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

풀이

조합을 이용해서 풀었다.
0~10개의 수를 1개~10개전부까지 조합을 통해 나열하게 된다면 (1,4,6) (2,5,9) 이런식으로 작은 수부터 큰수로 나열되게 된다 . 이 조합들을 거꾸로 문자열로 더해주면 641,952 .. 로 나타낼 수 있고 정렬을 해주게 되면 index의 값을 알 수 있다.

import sys
sys.stdin = open('input.txt')
from itertools import combinations


nums = [0,1,2,3,4,5,6,7,8,9]


result =[]
for i in range(1,11): # 한자리수부터 10자리수(9876543210) 까지 만들어줘야한다.
    combi = list(combinations(nums,i))
    while combi:
        numlist = combi.pop(0)  # 하나씩 뽑아서
        re = ""
        for j in range(len(numlist)-1,-1,-1):# 뒷자리 수부터 하나씩 더해주기
            re+=str(numlist[j])
        result.append(int(re))

result = sorted(result) # 정렬해주게 되면 작은 수부터 나열된다.


N = int(input())

try:
    print(result[N])
except:
    print(-1)

오답

0부터 모든 수를 다 하나씩 확인해서 그 값이 감소하는 수인지 찾아보았다. (브루트포스) ->시간초과

import sys
sys.stdin = open('input.txt')
N = int(input())
result = [0]

num = 0
# num이 100 000 000 0 보다 작아야한다.
# num 이 9876543210 보다 크면 그만
while len(result) <= N:
    if num > 1000000000:
        print(-1)
        exit()

    snum = str(num)
    flag=True

    if int(snum[0]) <= len(snum): # 210 세자리 수의 첫 수가 길이보다 작다면?
        num+=1
        continue

    while len(snum) > 1:
        first = snum[0]
        for i in snum[1::]:
            if int(first)<=int(i):
                num+=1
                flag=False
                continue
        snum = snum[1::]

    if flag==True:
        result.append(num)
    num += 1

print(result)
print(result.pop())