[BOJ] [JAVA] 1038번 감소하는 수

1038번: 감소하는 수

1. 문제

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

2. 생각

자연수 n이 감소하는 수라면 n % 10 > i >= 0인 i에 대해서 n * 10 + i도 감소하는 수임을 이용했다.

n % 10 == 0이라면 i가 없으므로 종료한다.

n에 0부터 9까지 차례대로 넣어 감소하는 수 list를 만들고 오름차순으로 정렬했다.

findDecreasingNum( n )은 결국 숫자 n으로 시작하는 모든 감소하는 수를 찾겠다는 의미이다.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 집합에서 선택된 수를 조합하면 감소하는 수는 하나로 특정되기 때문에 감소하는 수는 1023개임을 알 수 있다.때문에 1022번째가 마지막 감소하는 수이다.

3. 코드

package B;

import java.util.*;
import java.io.*;

public class Main {
    static List<Long> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if (n > 1022) System.out.println(-1);
        else {
            for (int i = 0; i < 10; i++) findDecreasingNum(i);
            Collections.sort(list);
            System.out.println(list.get(n));
        }
    }
    public static void findDecreasingNum (long n) {
        list.add(n);
        long d = n % 10;
        if (d <= 0) return;

        for (long i = d - 1; i >= 0; i--) {
            findDecreasingNum(n * 10 + i);
        }
    }
}