[Python/파이썬] 백준 1174번 줄어드는 수

1174번: 줄어드는 수

 

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

코드

BFS

from collections import deque

n = int(input())

desc = []  # 줄어드는 수
q = deque()
for i in range(10):
    desc.append(i)
    q.append(i)

while q:
    now = q.popleft()
    if len(desc) > 1_000_000:
        break
    last = now % 10
    for i in range(last):
        nx = now * 10 + i
        desc.append(nx)
        q.append(nx)

if n-1 < len(desc):
    print(desc[n-1])
else:
    print(-1)

 

1,000,000번째 줄어드는 수까지 구하기 위해 BFS를 사용했다.

 

초기 q에 한 자리수인 줄어드는 수들을 넣어놓고 q의 앞에서부터 pop하며 pop한 수의 뒤쪽에 숫자를 하나 붙여서 만들 수 있는 줄어드는 수를  desc에 저장했다.

10으로 나눈 나머지가 now의 끝자리 수이므로 이 수보다 작은 수를 끝에 붙이면 또 다시 줄어드는 수가 된다. 초기 q에도 오름차순으로 수를 넣어놓았고, BFS 안에서 now에 숫자 하나를 붙여서 nx를 만들 때에도 작은 수부터 붙이기 때문에 desc에는 오름차순으로 숫자가 들어가게 된다.

 

이렇게 모든 줄어드는 수를 구한 뒤 문제에서 요구하는 n번째 줄어드는 수를 desc에서 출력해주면 된다.

 

 

DFS

n = int(input())

desc = []


def dfs(num):
    desc.append(num)
    last = num % 10
    for i in range(last):
        dfs(num*10+i)


for i in range(10):
    dfs(i)

desc.sort()

print(desc[n-1] if n-1 < len(desc) else -1)