[Python] 백준 1038 감소하는 수 - 순열, 조합

백준 홈페이지 문제와 개인적인 풀이를 작성한 글입니다.

 

백준문제 - 1038 : 감소하는 수

1038번: 감소하는 수

---

에피소드

이번 문제의 경우에는, 순열과 조합의 조합이라는 것을 사용한다. 고등학교에서 나오는 그 순열과 조합의 조합이 맞습니다. 해당 내용은 라이브러리를 이용해서 간단하게 사용할 수 있습니다. 조합에 대해서는 다음 글에서 이론 내용을 자세하게 설명해 보도록 하겠습니다.

 

필자는 이 문제를 틀렸고, 시간도 굉장히 오래걸려 풀지 못했습니다. 다른 분들의 풀이들을 참고하여 가장 간단하고 기발하다고 생각되는 것을 가져와서 작성하였습니다.

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1	예제 출력 1
18	42

 

예제 입력 2	예제 출력 2
0	0

 

예제 입력 3	예제 출력 3
500000	-1

 

코드

import sys
from itertools import combinations

input = sys.stdin.readline

# 번째 수 입력받기
n = int(input())

# 리스트 만들기
result = []

# 1 개 부터 10 개 숫자의 조합을 만들어야하기 때문에 다음과 같이 범위를 설정합니다.
for i in range(1, 11):
  # 9 8 7 6 5 4 3 2 1 0 이기 때문에 총 숫자는 10개 입니다.
  for j in combinations(range(0, 10), i):
    temp = sorted(list(j), reverse = True)
    result.append(int("".join(map(str, temp))))

result.sort()

if len(result) > n:
  print(result[n])

else:
  print(-1)