백준 1174번: 줄어드는 수

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

문제 풀이

BFS

count = 현재 큐에 들어가는 수가 몇 번째 줄어드는 수인지

num = 현재 큐에서 꺼낸 줄어드는 수

lastDigit = num의 마지막 자리의 수

next = 마지막 자릿수를 제외한 나머지 자릿수가 num인 줄어드는 수

N이 10보다 작거나 같으면 N - 1이 N번째 줄어드는 수이므로 출력

두 자리 이상의 줄어드는 수는 맨 뒷자리가 그 앞에까지의 수의 맨 뒷자리보다 작은 수가 오도록 만들어지므로 큐에 한 자리의 줄어드는 수를 순서대로 집어넣고 하나씩 꺼내 그 수가 맨 뒷자리를 제외한 나머지 자리가 되는 수를 순서대로 큐에 집어넣어 N번째 수를 찾음

N번째 수를 찾으면 출력, 아니면 -1 출력하면 정답

풀이 설명

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

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

줄어드는 수를 순서대로 보면 0부터 9까지의 한 자리 수가 있고 그 뒤에 10부터 시작하는 두 자리 수가 있다. 뒤로 갈수록 점점 자릿수가 많아지며 이 수들을 맨 뒷자리와 그 앞에까지의 수로 나눴을 때 앞에까지의 수도 줄어드는 수이고 맨 뒷자리 수가 그 앞자리까지의 수의 맨 뒷자리보다 작은 수로 이루어진다는 것을 알 수 있다.

따라서 큐에 한자리인 줄어드는 수를 순서대로 넣어놓고 큐에 앞에서부터 수를 하나 꺼내서 그 수의 맨 뒷자리 수 보다 작은 수를 맨 뒷자리에 붙여서 큐에 새로 넣으면 모든 줄어드는 수를 순서대로 탐색할 수 있다.

또한 큐에서 수를 꺼낼때 수를 세는게 아니라 넣을 때 순서를 세는게 탐색 횟수를 줄이는 방법이므로 N이 10보다 작거나 같다면 N - 1을 출력하고 아니라면 큐에 진입되는 N번째 수를 찾을때까지 탐색해 그 수를 출력하거나 없다면 -1을 출력하면 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    val queue = ArrayDeque<Long>()
    for(i in 0L.. 9L){
        queue.add(i)
    }
    if(N <= 10){
        println(N - 1)
        return
    }
    var count = 10
    while(queue.isNotEmpty()){
        val num = queue.removeFirst()
        val lastDigit = num % 10
        for(i in 0 until lastDigit){
            val next = num * 10 + i
            count++
            if(count == N){
                println(next)
                return
            }
            queue.add(next)
        }
    }
    println(-1)
}