[JAVA] 백준 감소하는 수

1023개를 꼭 알아야할 필요는 없다.

처음에는 하나씩 증가하면서 수를 순서대로 잘라서 넣어주는 방식으로 진행했다.

하지만, 그런식으로 진행하게되면 최대값이 몇인지 몰랐고, 효율성 측면에서 순열이 더 좋다고 하여 방식을 바꾸었다.

 

 

각각의 경우에 대하여 일의자리 수에 따른 경우의 수를 구한다

 

일의자리수 각각에 대하여 아래와 같은 방식으로 미리 계산한다.

0: 0

1: 1, 10

2 : 2, 20, 21, 210

3 : 3, 30, 31, 32, 310, 320, 321

...

 

참고로 가장 큰 숫자는 9876543210 이다.

즉, 열자리 숫자이며 이 경우 2^10 -1 = 1024-1 = 1023개이다.

list.size()를 출력해보면 위 결과를 얻을수 있었다.

1023개를 꼭 알아야할 필요는 없다.

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

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));
​​​​​​​​StringTokenizer st = new StringTokenizer(br.readLine());
​​​​​​​​n = Integer.parseInt(st.nextToken());
​​​​​​​​list = new ArrayList<>();

​​​​​​​​if (n <= 10) System.out.println(n);//1의자리는 시간단축용용
​​​​​​​​else if (n > 1022) System.out.println(-1);
​​​​​​​​else {
​​​​​​​​​​​​for (int num = 0; num < 10; num++) {//1의자리가 0~9까지인 경우들
​​​​​​​​​​​​​​​​cal(num, 1);
​​​​​​​​​​​​}
​​​​​​​​​​​​Collections.sort(list);
​​​​​​​​​​​​System.out.println(list.get(n));
​​​​​​​​}

​​​​}

​​​​private static void cal(long num, int depth) {
​​​​​​​​if (depth > 10) {//9876543210 : 최대 10자리
​​​​​​​​​​​​return;
​​​​​​​​}
​​​​​​​​list.add(num);

​​​​​​​​for (int i = 0; i < 10; i++) {
​​​​​​​​​​​​if (num % 10 > i) {//각각의 경우의수를 다 넣어줌
​​​​​​​​​​​​​​​​cal((num * 10) + i, depth + 1);
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return;
​​​​}

}