백준1038_감소하는 수

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 

18

예제 출력 

42

[코드]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static long cur;
    public static long number;
    public static int N;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        if (N > 1022){
            number = -1;
        }else if(N > 0) {
            getFirst();
        }
        System.out.println(number);
    }
 
    public static void getFirst() {
        int cnt = 0;
        while (true) {
            for (int i = 1; i <= 9; i++) {
                getNumber(i, i, cnt);
                if (cur == N)
                    return;
            }
            cnt++;
        }
    }
 
    public static void getNumber(long total, int num, int cnt) {
        if (cnt == 0) { // 몇번 째 호출인지
            // 마지막 단계라는 뜻
            cur++;
            if (cur == N) {
                number = total;
                return;
            }
        } else {
            for (int i = 0; i <= num - 1; i++) {
                getNumber(total * 10 + i, i, cnt - 1);
                if (cur == N)
                    return;
            }
        }
    }
 
}
 
 

[알고리즘]

우선, 1부터 9까지 맨 앞자리 숫자는 getFirst() 함수에서 정해준다.

자리수 대로 getNumber 함수에서 개수를 세도록 만들어주었는데, total, num, cnt 라는 변수를 받는다.

이 getNumer함수는 재귀함수이다. total 은 지금까지 만들어진 진짜 숫자를 의미하고, num은 자기 바로 앞자리 숫자를 의미한다.

감소하는 수이므로 자기 앞자리 숫자보다 무조건 작은 수가 되어야 한다는 뜻이므로, 0부터 num-1 까지 또 getNumber를 재귀호출하게 된다.

cnt 는 자리수가 몇자리가 남았는지를 의미한다. 마지막 자리수까지 올 수 있다면 그것은 유효한 숫자라는 말이다. 

이런 숫자를 발견할 때마다 cur 라는 전역변수를 하나씩 증가시키게 만들었는데, 이것이 N (즉, 입력값) 과 같다면 이게 문제에서 요구하는 답이라는 말이다.

그래서 모든 함수를 다 중단시키고 빠져나와 이 값을 출력한다.