1174 줄어드는 수 (Java)

줄어드는 수

문제

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

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

입력

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

출력

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

풀이

dfs를 통해 모든 줄어드는 수를 리스트에 저장한 후, 정렬하여 사용한다.
dfs 구현 방식은

1. 9부터 0까지 내림차순으로 정리되어 있는 배열을 하나 선언한다.
2. dfs함수를 두개의 인자로 사용하여 구현한다. 첫 인자는 현재까지의 합 (sum)이고 두번째 인자는 사용할 수의 인덱스 (idx)이다. 이 때 sum은 최대 9876543210이므로 long으로 선언한다. ex) dfs(long sum, int idx)
3. 종료 조건은 idx >= 10이다. idx가 10이면 1번째 과정에서 선언한 배열의 크기를 벗어나기 때문이다.
4. sum으로 들어온 수가 리스트에 저장되어 있지 않다면 저장한다.
5. 재귀 함수를 호출한다. 
   1.  현재 수를 사용하여 새로운 수를 만들어 재귀함수를 호출한다.
   2.  현재 수를 사용하지 않고 재귀함수를 호출한다.
      이 방식으로 dfs를 구현하면 모든 감소하는 수를 만들 수 있다. 그러나 정렬되어 있지 않은 상태이므로 정렬이 필요하다.
      dfs가 동작을 마치고 나서 list를 정렬해준다.

위의 과정을 마친다면 n의 값을 구하면 된다.
만약 모든 감소하는 수보다 n의 값이 크다면 -1을 반환해야 하므로 if(n > list.size())를 통해 계산해준다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main{

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        dfs(0, 0);

        Collections.sort(list);

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

    static void dfs(long sum, int idx) {

        if (!list.contains(sum)) {
            list.add(sum);
        }
        if (idx >= 10) {
            return;
        }

        dfs(sum * 10 + num[idx], idx + 1);
        dfs(sum, idx + 1);
    }
}