백준 1038번 감소하는 수 JAVA

링크텍스트

설명

현재 자리에서 index - 1까지 반복하면서 모든 경우의 수를 재귀적으로 탐색하였다.
시간복잡도: O(1), 공간복잡도: O(1)

코드

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

class Main {
		static ArrayList<Long> al = new ArrayList<>();
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());

		makeNumber();

		Collections.sort(al);

		if(n>=al.size()){
			System.out.println(-1);
		}else{
			System.out.println(al.get(n));
		}
    }

	public static void makeNumber(){
		for(int i=0;i<=9;i++){
			dfs(i,i);
		}
	}

	public static void dfs(long num, int index){
		al.add(num);

		for(int i=index-1;i>=0;i--){
			dfs(num*10+i,i);
		}
	}
}