백준 1038번 감소하는 수 풀이/해설/코드 (파이썬) 다소 까다로운 재귀 + 구현문제

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

문제 풀이는 스킵!

 

우선 문제를 보면 바로 알겠지만 적당히 재귀나..브루트포스같은걸 활용하면 되겠거니 싶지만 구현이 다소 귀찮거나 어려울거라는 감이 딱 오는..문제이다. 내가 푼 방법은 두개가 있는데, 위의 풀이부터 설명하자면

 

1. 10의자리까지만 감소하는 수가 가능하므로 1~10의 자릿수..의 길이에 따라서 반복하는데,

2. 맨 앞자리는 아무 숫자나 와도 되고, 그 뒤부터는 앞자리보단 작은 수가 오도록 한다. 

3. 자릿수가 전부 채워질 때마다 숫자를 1씩 카운트 하고 우리가 원하는 숫자만큼 오면 해당 수 반환 후 프로그램 종료.

4. 3번에서 해결이 안나면 -1 출력 후 종료.

 

처음에 엄청 어렵게 생각했는데 잘 생각해보면 생각보단 풀만한 문제이다.

 

두번째 풀이는 내가 고안한건 아니고 찾아보다가 좋은 풀이가 잇길래 나도 구현해봤다.

 

1. itertools를 이용해 0부터 9까지의 숫자로 구성된, 한자리 짜리 수 ~ 9자리짜리 수만큼의 조합을 만들고

2. 이 조합은 보통 0,3,6 이런식으로 나오니까 역순으로 내림차순 정렬해주고 int로 저장.

3. 모든 조합이 나오면 저장된 모든 조합을 오름차순으로 정렬하고 만약 우리가 찾는 인덱스(숫자)가 있으면 해당 수 반환, 아니면 -1을 반환한다.

 

itertools를 이용하는 경우, 0,1 / 0,2 / 0,3 ... / 1,2 / .. 이런 식으로 나와서, 각각의 역순을 취한다 해도 2, 0 다음에 2,1이 아니라 3,0이 오게 된다. 따라서 마지막에 모든 값에 대해서 오름차순으로 정렬해줘야 우리가 원하는 값이 나온다.

 

이 때, str값으로 저장하면 41 다음에 42가 아니라 410이 오기 때문에 반드시 숫자로 값을 저장해둬야 한다.

 

첫번째 풀이가 더 나다운 풀이이긴 한데 두번째 풀이도 정말 놀랍다. 사실 백준 문제들이 워낙 코딩테스트를 준비하는 사람들이 많이 풀어보는 문제들이기도 하고 학원에서도(아마도..?) 백준 문제로 가르치는 경우가 많은 것 같아서, 일부 문제는 다른사람들의 코드가 궁금해서 검색해봐도 도통 정말.. 미세한 코드 논리 하나하나까지 다 똑같이 짜여진 경우가 많은데 이 문제는 그렇지가 않아서 좋았다.