백준1038 - 감소하는 수 Python

https://www.acmicpc.net/problem/1038

해당 문제는 문제에서 말하는 감소하는 수를 구한 뒤, N번째 감소하는 수를 출력하는 문제다.

 

문제 해결 방식

먼저 '감소하는 수'를 담을 배열을 구현한 뒤, 재귀함수를 만들어 '감소하는 수'를 담도록 했다. 해당 재귀함수는 아래와 같은데, 가장 끝에 있는 수를 뽑은 뒤 이보다 작은 수만 순회하여 다시 재귀함수를 동작시키는 방식으로 구현했다. 이때 문제에서 얘기하는 '감소하는 수'의 최댓값은 9876543210 이므로, 이를 이를 탈출 조건으로 지정하였다.

  def act (n) :
    if n > 9876543210 : return
    storage.append(n)
    limit = int(str(n)[-1])
    for i in range(limit) : 
      act(n * 10 + i)
  
  for i in range(10) :
    act(i)

 

이후 감소하는 수에 있는 배열을 정렬한 뒤, 주어진 N이 배열의 크기보다 작다면 해당 배열의 인덱스 N을 출력하도록 하고, 그렇지 않다면 -1을 출력하는 방식으로 로직을 완성했다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  N = int(data[0])
  
  storage = []
  def act (n) :
    if n > 9876543210 : return
    storage.append(n)
    limit = int(str(n)[-1])
    for i in range(limit) : 
      act(n * 10 + i)
  
  for i in range(10) :
    act(i)
  
  storage.sort()
  print(storage[N] if N < len(storage) else -1)
          
solution(input_data)