[백준] 1038 감소하는 수(Python)

백준 - 1038 감소하는 수

문제

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

입력

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

출력

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

예제

---

풀이 1

첫 번째 접근법

알고리즘 분류가 브루트포스 ? 오케이~ 하고 for 문으로 다 돌렸지만! 당연하게 실패했다!
생각보다 수가 커서 시간초과가 났다.... 아니 원래 브루트포스는 다 도는거 아닌가여? 시간 당연 오래 걸리는거 아니냐고요 ㅠ 시간초과...... ㅠ..... 너무해

정말 단순하게 생각했다

1. for문을 1 부터 9876543210 까지 돌리면서
2. 숫자를 문자열로 바꾼 후
3. 각 자리수마다 앞자리수와 뒷자리수를 비교한다
   3-1. 앞자리수 > 뒷자리수 이면 cnt 증가
   3-2. 앞자리수 <= 뒷자리수 이면 넘어간다
4. cnt == N 이면 출력하고 종료한다

문제점

1. 극악악악의 효율
2. 시간초과
3. python을 활용하지 못하고 C로 푸는 것 같은 느낌
4. 1023번째 값은 없다 ➡️ 이걸 굳이 계산해서 코드에 써넣을거면 뭐하러 코딩하냐.. 이런 코드 제일 싫어함(내가)
5. 그럼에도 어떻게든 시간을 줄여보고 싶어서 넣었다 ^^~... (내가 계산한거 아님. 다른 사람 질문검색 보다가 나옴)
6. 처음에 MAX 값을 어떻게 잡아야 할 지 몰라서 고민하다가 예제에 50만 넣으면 -1 나오길래 아~ 오키! 하고 50만으로 잡았다... MAX는 N이랑 상관 없는데........... 이것도 질문검색 보다가 알았다! 9876543210 ➡️ 유레카 그잡채🫢

결론

멍청한 나.. 갈길이 멀다.. 하지만 괜찮다! 공부하면 되니까!

극악의 효율이지만 어떻게 개선 좀 해볼까? 하다가 관뒀다
애초에 좋은 방법은 아니였다

그렇게 다른 사람의 코드를 공부하기로!
🥹

---

풀이 2

어떤 선생님의 엄청난 접근법을 봤다!

조합으로 해결하셨다....... 대박적

내가 얼마나 갇힌 생각으로 코딩했는지 느낀 순간이었다

어떻게 풀어야 할지 감이 안 올때 백준 알고리즘 분류를 보고 푸는 편인데, 내 집착이 나를 망쳤다

조합의 ㅈ자도 생각 못 함... 어감이 조금 그렇네

ssafy 준비할때 도대체 조합을 왜 코딩하면서 알아야할까 백번 생각했는데 역시.... 난 갈길이 멀다 ^^..... 언제쯤 따라가지? ㅠ

코드 풀이

1. combinations 함수 사용 ➡️ 중복을 제외한 조합
   combinations(list, n) : list 중에서 n개를 조합
2. for 문을 중첩해서 사용
   ➡️ (0) 부터 (0,1,2,3,4,5,6,7,8,9) 까지의 조합을 만듦
3. 만든 조합(튜플)을 거꾸로 정렬 후 문자열로 만듦
   ➡️ '0'부터 '9876543210'까지의 문자열 만듦
4. 만든 숫자를 int 타입으로 캐스팅해서 리스트에 저장
   ➡️ 0, 1, 10, 2, 20, ... 의 순서
5. 리스트를 정렬
   ➡️ 0, 1, 2, 3, 4, ... , 9876543210 의 순서

그저.. 대박

엄청 빠르고 간단하다!!!!!! 엄청 간결하고 쿨한 코드에... 덧붙일 말이 없음 🥹
이런건 무조건 배워야 돼!!!!!!!

---

코드

from itertools import combinations

N = int(input())

result = []
for i in range(1, 11):
	for j in combinations(range(10), i):
		num = ''.join(list(map(str, reversed(list(j)))))
		result.append(int(num))

result.sort()
if N >= len(result):
	print(-1)
else:
	print(result[N])

---

오늘도 내 힘으로 풀어내진 못했지만 combinations으로 풀어낸 걸 처음 접해서 많이 배웠다.
조합.. 아직도 잘 모르는데, 심지어 코드에서 적용하니까 이렇게 간단하게 풀 수 있다는 게 너무 신기하고!

그동안 내가 코딩을 바보같이 했다는 생각이 들었다.

왜 이렇게 C언어 풀이방법으로만 풀라는 건지 ㅠ___ㅠ
나름 python 좀 한다 생각했는데 자만했다

백준 gold 레벨로 가면서 다른 사람 풀이를 꼭 보게 되는데,
한 편으로는 너무 구글에 의존하나 싶다가도,
이런 새로운 방법을 배우는게 백배 이득이라 생각한다..
왜냐면 내 방식은 너무 구려

내일도 풀어야하는데 벌써 걱정!

그렇지만 화이탱ㅇㅇㅇㅇㅇㅇㅇㅇㅇ!