[ BOJ ][JAVA][1174] 줄어드는 숫자

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1366	515	432	41.659%

문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. (가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.)

입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

예제 입력 1

1

예제 출력 1

0

코드

비트마스킹 풀이

// 줄어드는 수.
import java.io.*;
import java.util.*;
public class p1174 {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] num = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        ArrayList<Long> arr = new ArrayList<>();
        // 2^10 만큼의 모든 경우의 수를 만든다.
        for (int i = 1; i < (1<<10); i++) {
            long sum = 0;
            // 10 자리 만큼 탐색한다.
            for (int j = 0; j < 10; j++) {
                // i가 0^2, 1^2, 2^2 .... j^2 승보다 크다면
                // -> i에 해당하는 비트가 각각 어느 위치(몇 번째 자리)에 비트를 가지고 있는지 체크
                // if문을 만족한다고 해당 자릿수가 존재한다는 것이므로 sum*10 + num[j]를 추가.
                if ((i & (1 << j)) > 0) {
                    sum = sum * 10 + num[j];
                }
            }
            arr.add(sum);
        }

        Collections.sort(arr);
        if (n > arr.size()) {
            System.out.println("-1");
            return;
        }
        System.out.println(arr.get(n - 1));
    }
}

재귀 풀이

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    static ArrayList<Long> list = new ArrayList<Long>();
    static int[] num = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        descNum(0, 0);
        list.sort(null);
        if (N > 1023)
            System.out.println(-1);
        else
            System.out.println(list.get(N - 1));
    }
    private static void descNum(long sum, int idx) {
        if (!list.contains(sum))
            list.add(sum);
        if (idx >= 10)
            return;
        descNum((sum * 10) + num[idx], idx + 1);
        descNum(sum, idx + 1);
    }
}