감소하는 수의 조건은 뒤에 오는 숫자가 앞에 숫자보다 작으면 된다.
이것을 생각해서 지금 숫자 num의 1의자리(곧 10의자리가 될 숫자)보다 작은 수만 새로 1의 자리에 들어갈 수 있기 때문에 새로 고려해서 추가해준다. 그런 식으로 모든 수를 구하고 정렬해주면 N번째 수를 구할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
static int N;
static ArrayList<Long> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
list = new ArrayList<>();
// 10보다 작은 경우
if (N < 10) System.out.println(N);
// 1022번째 숫자가 9876543210이기 때문에 1022번째보다 클 경우 -1
else if (N > 1022) System.out.println(-1);
// 재귀함수를 이용해서 9876543210이하의 감소하는 수를 모두 만들어준다.
else {
for (int i = 0; i < 10; i++) {
makeNum(i);
}
Collections.sort(list);
System.out.println(list.get(N));
}
}
public static void makeNum(long num) {
if (num > 9876543210L) return;
list.add(num);
for (int i = 0; i < num % 10; i++) {
makeNum((num * 10) + i);
}
}
}
숫자 바로 뒤에 올 숫자를 결정하면 되는 단순한 재귀함수 문제였는데 다음부터는 더 빨리 생각날 수 있도록 더 열심히 연습해야겠다.