[백준] 1038 - 감소하는 수

문제 링크

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

문제 요약

주어진 문제는 음이 아닌 정수 XXX에서 가장 큰 자릿수부터 작은 자릿수까지 자릿수가 순차적으로 감소하는 "감소하는 수"를 찾는 문제입니다. 예를 들어, 321과 950은 감소하는 수이지만, 322와 958은 그렇지 않습니다. 이 문제에서는 NNN번째 감소하는 수를 찾는 것이 목표입니다. 만약 NNN번째 감소하는 수가 존재하지 않는다면 -1을 출력해야 합니다.

입력: 자연수 N (0 ≤ N ≤ 1,000,000)

출력: N번째 감소하는 수 또는 해당 수가 존재하지 않을 경우 -1 출력

푼 방법

사용한 접근 방식은 다음과 같습니다:

1. Deque 사용: 각 감소하는 수를 생성하고 추적하기 위해 deque를 사용하여 큐 형태로 관리합니다.
2. 포지션 변수 사용: pos 변수를 통해 현재 몇 번째 감소하는 수인지 추적합니다.
3. 0-9 초기 추가: 초기에는 각 자릿수 0에서 9까지의 감소하는 수를 추가하며 pos 변수를 증가시킵니다. 만약 pos가 입력한 N과 같아지면 해당 수를 출력하고 종료합니다.
4. 큐의 pop과 append 활용: 그 이후로는 deque에서 가장 앞의 수를 꺼내 (popleft) 해당 수의 마지막 자릿수를 기준으로 다음 감소하는 수를 만듭니다. 마지막 자릿수보다 작은 수들을 뒤에 붙여서 새로운 감소하는 수를 생성하고, 다시 큐에 추가하며 pos 변수를 증가시킵니다.
5. 종료 조건: 만약 pos가 N과 일치하게 되면 현재 감소하는 수를 출력하고 프로그램을 종료합니다. 만약 큐가 비어 N번째 감소하는 수를 찾지 못할 경우 -1을 출력하고 종료합니다.

정답 코드

from collections import deque

n = int(input())

descending = deque()
pos = -1

while True:
    if pos < 9:
        for i in range(10):
            descending.append(i)
            pos+=1
            if pos == n:
                print(descending[-1])
                exit()
    else:
        if len(descending)>0:
            next = descending.popleft()
        else:
            print(-1)
            exit()
        chk_num = list(map(int, str(next))).pop()
        if chk_num == 0:
            continue
        for i in range(10):
            if chk_num > i:
                descending.append(int(str(next)+str(i)))
                pos+=1
            if n == pos:
                print(descending[-1])
                exit()