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

문제

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

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

• 문제를 통해 중복은 허용하지 않는 다는 걸 확인
• 가장 큰 감소하는 수가 9876543210 즉, 10자리가 가장 큼

우선 줄어드는 수 모두를 탐색하는 것이 좋다. (브루트 포스 알고리즘)

단, 모든 수중에 줄어드는 수 그리고 또한 N번째 수를 찾는 것이다. (백트래킹)

List안에 모든 줄어드는 수를 집어 넣은 뒤에 정렬시켜서 N을 통해서 해당 값을 찾으면 된다

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

public class Main {
    static int N;
    static int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    static List<Long> list = new ArrayList<>();

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

        dfs(0,0);

        Collections.sort(list); // 정렬해줘야 처음 부터 넣어짐


        if (N > list.size()) {
            System.out.println(-1);
        } else {
            System.out.println(list.get(N - 1)); // N번째 index
        }
    }

    private static void dfs(long num , int cnt) {

        if(!list.contains(num)){
            list.add(num);
        }

        //종료
        if (cnt == 10) {
            return;
        }
        //확장
        dfs((num * 10) + arr[cnt], cnt + 1); // arr배열이 9~0 으로 내림차순임으로 줄어드는수 보장됨

        dfs(num, cnt + 1); // 선택안하는 경우

    }
}

풀이

• 중복이 불가능 하고 내림차순으로 탐색되는것 !! (cnt (arr의 index) 늘리며 탐색!)
• arr 이 9~0 내림차순임으로 줄어드는 수 보장해준다
• 9876543210 은 long 타입 범위이다