문제

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

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력
첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 1
18
예제 출력 1
42

예제 입력 2
0
예제 출력 2
0

예제 입력 3
500000
예제 출력 3
-1

접근

완전 바보짓을 한 문제였다 하하,,,,,
나는 이 문제가 가장 작은 감소하는 수부터 N번째 감소하는 수가 나올 때까지 하나씩 해보는 일반적인 탐색 문제일 거라고 생각했다.
그래서 하나씩 해보려고 했는데,, 단순 재귀로는 감소하는 수를 오름차순으로 순서대로 구하는 게 생각보다 너무 어려웠다. 차라리 내림차순으로 구하는 거면 가능했을지도 모르겠다. 그런데 각 자리 숫자는 감소해야 하는데 그 수 자체는 오름차순이라 더 커져야 하니 너무 복잡해서 머리가 터질 거 같았다...

그래서 결국 풀이를 봤는데 이게 웬걸,,, 순서에 상관 없이 모든 감소하는 수를 일단 다 구한 다음 정렬을 하는 매우 간단한 방법이 있었던 거다.

이 문제의 핵심은 감소하는 수의 총 개수가 고작 1022개로 매우 적기 때문에 이것들을 브루트포스로 모두 구하더라도 큰 오버헤드가 없음을 간파하는 거였다.
감소하는 수의 최댓값인 9876543210가 꽤 큰 수다보니 감소하는 수도 많을 거라고 그냥 1차원적으로만 생각해버렸다....ㅠ

구현

순서에 상관 없이 일단 다 구하기만 하면 된다고 생각하니 구현이 훨씬 자유로워졌다.
수의 맨 앞자리를 first라고 하고, 이 first 값을 0부터 9까지 1씩 증가시켜가며 first로 시작하는 감소하는 수들을 모두 구하는 식으로 구현을 했다.

k로 시작하는 모든 감소하는 수에는 일단 k 자기 자신이 있을 것이다. 그리고 나머지는

• 0으로 시작하는 모든 감소하는 수들
• 1로 시작하는 모든 감소하는 수들
• 2로 시작하는 모든 감소하는 수들
  ...
• k - 1로 시작하는 모든 감소하는 수들

의 맨 앞에 k를 붙인 것이다.
0 ~ k - 1로 시작하는 모든 감소하는 수들을 하나씩 불러와 앞에 k만 붙여서 새로운 리스트에 저장하는 거다.

53210이라는 감소하는 수의 맨 앞에 8을 붙여서 853210을 만든다고 해보자.
그러려면 일단 8 뒤에 53210의 자릿수만큼 0을 붙여서 800000를 만든 다음 53210을 더하면 된다.
이를 토대로 기존의 감소하는 수를 num이라고 하고 이 앞에 first를 붙이기 위한 식을 세우면
first * 10^(num의 자릿수) + num
이 된다.
num의 자릿수를 구할 때는 num을 String으로 변환한 후 이 String의 길이를 구하는 방식(String.valueOf(num).length())을 사용했다.

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

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

        if (N <= 10) {
            System.out.println(N);
            return;
        }
        if (N > 1022) {
            System.out.println(-1);
            return;
        }

        List<Long>[] lists = new List[10];
        for (int i = 0; i < 10; i++) {
            lists[i] = new ArrayList<>();
            lists[i].add((long) i);
        }

        List<Long> result = new ArrayList<>(lists[0]);
        for (int first = 1; first <= 9; first++) {
            for (int second = 0; second < first; second++) {
                for (long num : lists[second]) {
                    lists[first].add(num + first * (long) Math.pow(10, String.valueOf(num).length()));
                }
            }
            result.addAll(lists[first]);
        }
        Collections.sort(result);
        System.out.println(result.get(N));
    }
}