[백준 BOJ / Python] 1174번 줄어드는 수

문제

정수를 십진수로 표현할 때, 각 자리수가 왼쪽에서 오른쪽으로 감소하는 줄어드는 수 중 n번째로 작은 줄어드는 수를 구하는 문제이다.

예를 들어 54321나 654는 줄어드는 수이며, 544나 324은 줄어드는 수가 아니다.

 

풀이

• BFS로 n번째 작은 수까지의 모든 경우의 수를 찾아 정답을 도출 할 수 있다.
• BFS를 사용하는 이유는 작은 수부터 순차적으로 줄어드는 수를 생성하므로, 추가적인 정렬 없이도 오름차순으로 n번째 줄어드는 수를 찾을 수 있기 때문이다.
• 먼저 한 자리수 (0~9)를 큐에 넣는다.
• 큐에서 줄어드는 수를 꺼내어 해당 숫자가 n번째 줄어드는 수라면 탐색을 멈추고 결과를 반환한다.
• 아니라면, 1의 자리보다 작은 숫자를 뒤에 추가해 새로운 줄어드는 수를 생성한다.
• 만약 n번째 줄어드는 수가 없다면 -1을 출력한다.

Python 코드

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())

q = deque(list(range(10)))
idx = 0
while q:
    x = q.popleft()
    idx += 1
    if idx == n:
        print(x)
        break

    # 1의 자리수보다 작은 숫자만 뒤에 더함
    for nx in range(x % 10):
        q.append(x * 10 + nx)
else:
    print(-1)

 

문제출처

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