[백준] 1038. 감소하는 수 - Python3

문제 설명

9876543210과 같이, 자릿수가 점점 감소하는 N번째 수를 구하는 문제

 

• 알고리즘 분류 - 브루트포스, (백트래킹?)
• 난이도 - 골드5

---

접근 방법

1. Brute Force

브루트포스로 접근하는 방법이 두 가지 생각났다.

 

1) 0부터 시작해 실제 정수를 문자열화해서 자릿수를 일일이 비교하는 방법 => 시간 초과

시간복잡도는 구하기가 애매한데... 9876543210까지의 수마다 문자열화 하고(logN) 각 자리수를 비교했으니 당연히 시간 초과가 났다.

 

2) 가장 큰 자리수의 수보다 작은 수를 뒤에 붙여가는 방법

예 - 0, 1, 10, 2, 20, 21, 210, ...

0~9까지 맨 앞자리를 설정하고, 맨 앞자리수보다 작은 수들의 모든 부분집합을 구해 각 부분집합을 문자열화 -> 역순 정렬 -> 정수화 해서 풀었다.

 

---

답안 코드 - Brute Force

메모리: 30748 KB , 시간: 36 ms, 코드 길이: 634 B

import sys
from itertools import combinations

def find_incline(N):
    cnt = 0

    inclines = []

    for start in range(10): # 맨 앞자리 0~9 설정
    	# 맨 앞자리보다 작은 수들 문자열화(문자열로 병합 및 정렬 예정이기 때문)
        smalls = [] 
        
        for i in range(start):
            smalls.append(str(i))
        
        # 부분집합 구하기
        combi = []
        
        for i in range(start+1):
            combi += list(combinations(smalls, i))
        
        # 부분집합 문자열화 -> 역순정렬 -> 맨 앞자리 붙이고 정수화
        for tup in combi:
            inclines.append(int(str(start)+''.join(tup)[::-1]))
    
    inclines = sorted(list(set(inclines)))
    
    if N >= len(inclines):
        return -1
    else:
        return inclines[N]

N = int(sys.stdin.readline())
print(find_incline(N))