1038. 감소하는 수

문제

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

입력

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

출력

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

풀이

1. 중복되는 숫자가 들어간 경우, 감소하는 수가 아닌 것을 알 수 있다. 따라서 0~9까지의 숫자를 이용해 감소하는 수들의 조합을 모두 만들고 나서, N번째 수를 출력하면 된다.
2. 이 때, 조합들을 배열에 저장해 둘 수 있으며 N이 배열의 길이보다 길 때 즉, N번째 감소하는 수가 없을 때는 -1을 출력한다.

0~9까지의 숫자를 이용해 감소하는 수들의 조합을 어떻게 만들까?

[처음 사용한 방법 : 재귀호출]

• 함수에 인자로 들어온 수 - 1 ~ 0까지 반복문을 수행해 현재까지 만든 수 뒤에 붙여주면 감소하는 수를 만들 수 있다.
• 만들어진 조합을 decreasedNum에 저장한다고 하자.

  decreasedNum = [] 
  def recursive (preNum, number) :
  	for num in preNum-1 ~ 0 :
      	newNum = number * 10 + num
          decreasedNum.append(newNum)
          recursive(num, newNum)

[파이썬에서 제공하는 조합 생성 함수 이용]

• itertools의 combinations 함수는 사용하면 주어진 배열에서 n개를 뽑아 조합 리스트를 만들어준다.

  decreasedNum = []
  	for number in range(1,11) :
      	for comb in itertools.combinations(range(10), number) :
          	comb = list(comb)
              comb.sort(reverse=True)
              decreasedNum.append(int("".join(list(map(str,comb))))

코드

1. 재귀호출

n = int(input())
decreasedNum = []
def solve (preNum, currentNum) :
  for num in range(preNum-1, -1, -1) :
    newNum = currentNum * 10 + num
    decreasedNum.append(newNum)
    solve(num, newNum)

for i in range(9, -1, -1) :
  decreasedNum.append(i)
  solve(i, i)

decreasedNum.sort()
print(decreasedNum[n]) if n < len(decreasedNum) else print(-1)

2. itertools.combinations

import itertools

n = int(input())
decreasedNum = []
for number in range(1,11) :
  for comb in itertools.combinations(range(10),number) :
    comb = list(comb)
    comb.sort(reverse=True)
    decreasedNum.append(int("".join(list(map(str,comb)))))

decreasedNum.sort()
print(decreasedNum[n]) if n < len(decreasedNum) else print(-1)