[백준] 1038번 감소하는 수 파이썬(Python) 풀이

1038번: 감소하는 수

[문제]

---

[코드]

from itertools import combinations

N = int(input())
result = []
for i in range(1, 11):
    for temp in combinations(range(0, 10), i):
        temp = list(temp)
        temp.sort(reverse=True)
        result.append(int("".join(map(str, temp))))


result.sort()

try:
    print(result[N])
except:
    print(-1)

---

[해설]

백트래킹 문제이다

난이도는 골드5  : 비교적 쉬운 문제

 

문제의 핵심은 다음과 같다

일명 '감소하는 수'를 만들어 내는 것 

여기서 감소하는 수는 321 처럼 자릿수가 아래로 가면서 숫자가 낮아지는 수를 문제에서 의미한다

 

이를 위해서 itertools의 combinations를 import 해주었다 (순열을 만들어주는 함수)

이를 활용해서 1, 11까지 for문을 만들어 주고 각 자릿수의 감소하는 수를 구하기위해 순열을 만들어 준다

 

여기서 왜 1, 11까지일까? 

: 우리에게 주어진 숫자 (0 ~ 9)

이를 이용해서 하나씩 사용했을때 만들 수 있는 수의 자릿 수

최소 1자릿수 에서 최대 10자릿수를 만들어 낼 수 있다

 

따라서 두번째 for문을 통해서 각 자릿수의 순열을 만들어준다

그리고 이를 리스트로 만들어서 감소하는 수로 만들기 위해서 내림차순으로 정렬해준다

 

from itertools import combinations

N = int(input())
result = []
for i in range(1, 11):
    for temp in combinations(range(0, 10), i):
        temp = list(temp)
        temp.sort(reverse=True)
        result.append(int("".join(map(str, temp))))

ex) 만들어진 감소하는 순열

[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[1, 0]
[2, 0]
[3, 0]
[4, 0]
[5, 0]
[6, 0]
[7, 0]
[8, 0]
[9, 0]
[2, 1]
[3, 1]
[4, 1]

....

 

그리고 이렇게 만들어진 순열을 str으로 형변환해서 하나의 문자로 합쳐주고 

미리 만들어 놓은 rsult라는 리스트에 append해준다

 

따라서 우리가 원하는 감소하는 수가 만들어 졌다

 

아래의 예시가 우리가 만들어낸 감소하는 수 리스트이다

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 21, 31, 41, 51, 61, 71, 81, 91, 32, 42, 52, 62, 72, 82, 92, 43, 53, 63, 73, 83, 93, 54, 64, 74, 84, 94, 65, 75, 85, 95, 76, 86, 96, 87, 97, ....]

 

result.sort()

try:
    print(result[N])
except:
    print(-1)

 

이때 리스트 값의 순서가 뒤죽 박죽이기 때문에 오름차순으로 한번 정렬 해준다

 

그리고 try문을 활용해서 우리가 원하는 위치에 값이 있으면 그 값을 출력하고

없으면 -1을 출력하게 한다

 

 

 

참쉽죠? (●'◡'●)