감소하는 수 ( 1038 번 )

1038번: 감소하는 수

 

---

🧠 알고리즘

• 브루트포스 ( 조합 탐색 + 정 )

 

✔️ 동작 방식

• 사용할 숫자 집합을 ['9','8',...,'0']로 정의
• 길이가 1 ~ 10인 모든 조합을 생성 (combinations)
• 각 조합을 문자열로 합쳐 정수로 변환 → answer 리스트에 저장
• answer를 정렬해 증가하는 순서의 줄어드는 수 목록 완성
• n번째 값이 있으면 출력, 없으면 -1 반환

---

 

🧾 코드

import sys
from itertools import combinations

def _main():
    answer = []
    number = ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0']

    for com_num in range(1, 11):
        for combi in combinations(number, com_num):
            answer.append(int(''.join(combi)))

    answer.sort()
    if n >= len(answer):
        return -1
    else:
        return answer[n]

n = int(sys.stdin.readline().rstrip())
print(_main())

---

 

⏱️ 시간 복잡도

각 조합은 갯수는 >> 2 ** 10 - 1 = 1023

해당 알고리즘 시간 복잡도 : 상수시간 ( O(1) )