나의 순도 100% 짜리 풀이.

1. 내 풀이 - 성공

import sys
input = sys.stdin.readline

n = int(input())
digit = 1
num = []
decrease = []

def dfs(k):
    if len(num) == digit:
        decrease.append(int("".join(map(str, num))))
        return
    for i in range(k, -1, -1):
        if i not in num:
            num.append(i)
            dfs(i-1)
            num.pop()

while len(decrease) <= n:
    dfs(9)
    digit += 1
    if digit == 12:
        print(-1)
        exit()

decrease = sorted(decrease)
print(decrease[n])

아주 기쁘다. 이게 얼마만에 보는 순도 1000000000% 내 풀이인지 ㅠㅠ
너무나도 감격스러워 ~~~

사실 문제 분류는 브루트포스에 되어있던 문젠데,
아래에

이거 보고 오 백트래킹으로 풀 수 있구나 ~~~ 했었다.
그런데 당시에는 어떻게 백트래킹으로 접근해야 할지 몰랐다가! 좀 고민해보니까 백트래킹이 더 쉽다고 느껴진 것 !!!
그래서 바로 백트래킹으로 풀어버렸당 ~~

풀이 설명을 하자면,
digit 변수는 자릿수이다. 일단 내가 고민을 한바에 따르면, 자릿수 변수가 꼭 있어야 하기 때문에 일의 자리라는 것을 표시하기 위해 1로 초기화 해뒀고, num은 만들어질 숫자, 그리고 decrease는 만들어진 숫자가 들어가는 리스트이다.

dfs 함수에 k라는 변수를 통해 내림차순 정렬을 한다. 처음에는 오름차순을 했었다가, 내림차순으로 하는 게 더 쉬워서 내림차순으로 진행했다. dfs 함수와 관련된 부분은 나의 블로그 다른 포스팅에서 잘 설명해뒀으니 참고!

그리고 while 문을 통해서 decrease 라는 숫자 모음들의 길이를 n과 비교를 한다. 예를 들어 1의 자리만 추가된 decrease 리스트는 길이가 10으로 만약 n이 18일 때는 10의 자리의 숫자들까지 있어야지 18번째의 감소하는 수를 뽑을 수 있다.

그래서 digit에 1을 더해주게 된다. 주의해야 할 부분은 digit의 최댓값이다. 감소하는 수는 9876543210 으로 총 10개의 자릿수가 필요하다. 그래서 만약 digit이 12라면, 더 이상의 감소하는 수는 없으니 -1을 출력하고 코드를 종료해주도록 했다.

만약 이 조건문에 걸리지 않는다면 decrease를 정렬해서 n에 해당하는 감소하는 수를 찾으면 완료!

2. 다른 풀이 - 브루트포스

import sys
from itertools import combinations

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

nums = list()               # 모든 감소하는 수
for i in range(1, 11):      #  1~10개의 조합 만들기 (0~9개니깐)
    for comb in combinations(range(0, 10), i):  # 0~9로 하나씩 조합 만들기
        comb = list(comb)
        comb.sort(reverse=True)                     # 해당 조합을 감소하는 수로 변경
        nums.append(int("".join(map(str, comb))))

nums.sort()   # 오름차순

try:
    print(nums[n])
except:     # 인덱스가 넘어가는 경우 -1 출력. 마지막 수 9876543210
    print(-1)

풀이 출처: https://ryu-e.tistory.com/59

브루트포스를 이용해서 수를 다룰 때는 이렇게 combination 등의 itertools를 많이 쓰는 것 같다.
생각보다 괜찮은 듯 ...
다음에는 꼭 이런 식으로 브루트포스 알고리즘을 활용해서 풀어봐야겠다.

3. 마치며

추가로 깨달은 점: 골드4가 골드5를 풀면 5점을 준다.