백준 알고리즘 1038: 감소하는 수(Java)

풀이: 완전 탐색이라고 하지만 1부터 증가하여 찾는다면 제한시간에 걸릴 것이 분명하다.

일정 규칙내에서 재귀함수를 이용하여 풀어줬다

0으로 시작하는 감소수(사실 0 하나)

1로 시작하는 감소수 ex)10

2로 시작하는 감소수 ex)20, 21, 210

 

 

package Baekjoon;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main_1038 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
//        범위 내 최대 감소수는 987654321
        int idx = Integer.parseInt(str);
        if(idx > 1022){
            System.out.println(-1);
            return;
        }
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<10; i++){
            getDecNum(i, 1, list);
        }

        Collections.sort(list);


        System.out.println(list.get(idx));
    }

    private static ArrayList getDecNum(long num, int temp, ArrayList list){
        if(temp > 10){
            return list;
        }

        list.add(num);

        for(int i=0; i<10; i++){
            if(num%10 > i){
                getDecNum((num*10)+i, temp+1, list);
            }
        }
        return list;
    }
}