백준 1038 감소하는 수

 

감소하는 수 중에서 가장 큰 값은 9876543210 이고 1022번째 위치한다.

 

 * 첫번째 방법.

  0~9의 배열에서 시작

  각 숫자별로 해당 숫자*10이 되었을 경우 뒤에 올수 있는 숫자들을 구한다.

  1 : 0

  2 : 0,1

  3 : 0,1,2

  ...

  9 : 0,1,2,.....,8이 올 수 있다.

 

(각 수자 *10 + 올 수 있는 숫자)들을 반복해서 재귀호출 한다.

def f():
 global d,r
 l=[]
 
 for e in d:
  t=e%10
  for i in range(t): #마지막 자리는 앞 수보다 작은 수가 와야 함.
   l+=[e*10+i] # 앞의 수 *10 + 마지막 자리수
 
 d=l # 다음 재귀호출을 위해 대입
 r+=l # 결과배열에 추가
 if l:f() #감소하는 검토대상 수가 있을 경우 함수 재귀 호출

n=int(input())
d=[*range(10)] # 자리수가 동일한 감소하는 수의 배열들
r=d[::] # 감소하는 수 결과 배열

f()
print(-1if n>=len(r)else r[n])

 

exec 문을 이용하면 좀 더 짧게 구현 가능하다.

n=int(input())
d=[*range(10)]
t=d[::]

exec('t=[e*10+i for e in t for i in range(e%10)];d+=t;'*9)

print(-1if n>=len(d)else d[n])

 

* 두번째 방법 : 조합을 이용

   0~9 사이의 문자에 대해 combination을 이용하면 조합의 케이스를 모두 오름차순으로 리턴한다.  

   (최대 갯수 : 10개 선택)

 

  l = [0,1,2,3,4,5,6,7,8,9]
  for e in combinations(l,2): print(e)  # 2개만 선택할 경우

 

   ==> (0, 1) (0, 2) (0, 3) ... (8,9) 순으로 리턴

 

  for e in combinations(l,3): print(e) # 3개만 선택할 경우

 

  ==> (0, 1, 2) (0, 1, 3) (0, 1, 4) ... (7, 8, 9) 순으로 리턴

 

  해당 조합의 케이스들을 모두 Reverse 정렬하면 감소하는 수가 된다.

  (0, 1, 2) -> (2, 1, 0)

  ...

  (7, 8, 9) -> (9, 8, 7)

 

  위 Reverse된 조합의 각 숫자를 문자로 만들고 연결 후 ('210") 정수로 다시 변환 후 

  이렇게 만들어진 수들을 정렬해서 n 번째 위치를 찾을 수 있다.  

from itertools import *
n=int(input())
r=[] # 결과 배열

for i in range(1,11): # 고를 숫자 갯수, 최대 10개 가능
 for j in combinations(range(10),i): # 0~9의 숫자 중 i개를 고른다.
  num = ''.join([*map(str,[*j][::-1])]) # 조합의 각 케이스를 역순정렬/문자로 변환/합치기
  r+=int(num), # 정수로 변환 후 결과 배열에 추가

r.sort() # 결과배열 정렬

if n >=len(r): # n번째 감소하는 수열이 없다.
 print(-1)
else:
 print(r[n])