백준 1038번 - 감소하는 수

백준 1038번 - 감소하는 수

문제

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

입력

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

출력

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

풀이

9876543210보다 큰 감소하는 수는 없으므로 감소하는 수의 개수는 일정하다.

1. 숫자 1개부터 10개까지 combinations 함수를 이용해 모든 수의 조합을 만든다.
2. 수들을 역순으로 정렬한다.
3. 정렬된 수들을 합쳐서 리스트에 저장한다.
4. arr[n]출력을 시도하고 만약 실패한다면 n번째 감소하는 수가 없다는 뜻이므로 -1을 출력한다.

import sys
from itertools import combinations

n = int(sys.stdin.readline())

arr = []
for i in range(1, 11):
    for j in combinations(range(0, 10), i):
        temp = list(j)
        temp.sort(reverse=True)
        arr.append("".join(map(str, temp)))

arr = list(map(int, arr))
arr.sort()
try:
    print(arr[n])
except:
    print(-1)