백준 [자바 : java] 1038 : 감소하는 수

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

수를 입력받으면 감소하는 수 중 해당 수번째 감소하는 수를 출력하는 프로그램이다. 

처음에는 수학적인 규칙을 찾으려고 했지만 쉽지 않았고, 감소하는 수가 많이는 없다는 것을 알고, 모든 감소하는 수를 찾아 정렬하고 구하는 방식을 사용했다. 

 처음에는 순열을 이용해서 풀었는데 0을 다루는 과정에서 오류가 났다. arr에서의 순서대로 수를 구성하면 첫 자리가 0일 때를 간과하게 되기 때문이다. 그래서 방문 여부를 알려주는 vis를 이용해서 list에 감소하는 수를 넣고 이를 나중에 정렬하는 방식을 사용했다.

 

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


public class Main {

    static boolean[] vis;
    static int[] arr;

    static ArrayList<Long> list = new ArrayList<>();


    static void make(int now, int num, int k) {
        if (num == k) {
            change(k);
            return;
        } else {
            for (int i = now ; i <= 9; i++) {
                if (vis[i] == false) {
                    vis[i] = true;
                    arr[num] = i;
                    make(i+1,num + 1,k);
                    vis[i] = false;
                }
            }
        }
    }

    static void change(int k){
        long ans = 0;

        int pp = 0;

        for(int i = 0;i<10;i++){
            if(vis[i]){
                ans += i * Math.pow(10,pp);
                pp++;
            }
        }
        //System.out.println(ans);
        list.add(ans);
    }




    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());



        for(int i = 1; i<= 10;i++){
            vis = new boolean[10];
            // 1부터 10까지의 자릿수별로 계산
            arr = new int[i]; // 자릿수 계산할 때마다 배열 재생성
            make(0,0,i);
        }

        Collections.sort(list);

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

    }
}