[백준] 감소하는 수 (1038번)

코드 힌트

 

1. 감소하는 숫자란?
   • 감소하는 숫자는 각 자리 숫자가 왼쪽에서 오른쪽으로 갈수록 작은 숫자들로 이루어진 숫자입니다. 예를 들어, 321, 520, 10 등이 있습니다. 이 코드의 목적은 입력받은 n번째 감소하는 숫자를 찾아 출력하는 것입니다.
   • 감소하는 숫자의 개수는 제한적입니다. 가장 큰 감소하는 숫자는 9876543210이고, 이러한 감소하는 숫자의 최대 개수는 1022개입니다.
2. 숫자 생성 방법:
   • 처음에는 0부터 9까지의 숫자를 시작으로 각 숫자를 확장해 나갑니다. 확장 시, 숫자의 마지막 자릿수보다 작은 숫자들만 추가로 붙여야 감소하는 숫자가 됩니다.
   • 예를 들어, 숫자 5를 시작으로 할 때, 54, 53, 52, 51, 50과 같이 마지막 자릿수 5보다 작은 숫자들을 뒤에 붙여서 새로운 숫자를 만들 수 있습니다.
   • 이 과정을 재귀적으로 처리하는 방식이 사용되며, 각 자릿수를 확장해가면서 새로운 감소하는 숫자를 리스트에 저장합니다. 숫자의 자릿수가 10을 넘으면 더 이상 처리하지 않고 종료합니다.
3. 재귀 함수 동작 설명:
   • bp(long num, int idx) 메서드는 주어진 num을 기반으로 그 숫자보다 작은 자릿수를 추가하여 새로운 감소하는 숫자를 만드는 역할을 합니다.
   • 예를 들어, 32라는 숫자가 주어졌을 때, 마지막 자릿수 2보다 작은 1, 0을 뒤에 붙여 321, 320과 같은 새로운 숫자를 재귀적으로 생성하게 됩니다.
   • 이렇게 확장된 숫자들은 리스트 list에 모두 저장되고, 함수 호출이 끝나면 리스트는 모든 가능한 감소하는 숫자들을 포함하게 됩니다.
4. n번째 감소하는 숫자 찾기:
   • 리스트에 저장된 모든 감소하는 숫자들은 일단 정렬됩니다. 그 이유는 생성되는 순서가 반드시 크기 순서대로가 아니기 때문에, 정렬을 통해 정확한 순서대로 정렬된 후 n번째 숫자를 찾을 수 있게 됩니다.
   • 입력 n이 만약 1022보다 크다면 존재하지 않는 숫자이므로 -1을 출력합니다. 0부터 9까지는 그 숫자 자체가 감소하는 숫자이므로, n <= 10일 경우 그 숫자 그대로를 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

public class Main {

    static List<Long> list; // 감소하는 숫자를 저장할 리스트

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

        list = new ArrayList<>(); // 감소하는 숫자들을 담을 리스트 초기화

        int n = in.nextInt(); // 입력받은 n번째 감소하는 숫자
        if (n > 1022) { // 감소하는 숫자의 최대 개수는 1022개를 넘지 않음
            System.out.println(-1); // 1022를 넘으면 -1 출력 후 종료
            return;
        } else if (n <= 10) { // 0부터 9까지는 해당 숫자가 감소하는 숫자 자체임
            System.out.println(n); // n이 10 이하면 그 숫자 자체가 정답
            return;
        }

        // 0부터 9까지의 각 숫자로부터 감소하는 숫자를 만들어냄
        for (int i = 0; i < 10; i++) {
            bp(i, 1); // 현재 숫자와 그 숫자의 자릿수를 1로 시작
        }
        Collections.sort(list); // 생성된 감소하는 숫자들을 정렬
        System.out.println(list.get(n)); // n번째 감소하는 숫자 출력
    }

    // 재귀적으로 감소하는 숫자를 만들어내는 메서드
    public static void bp(long num, int idx) {
        if (idx > 10) return; // 자릿수가 10을 넘으면 종료

        list.add(num); // 현재 생성된 숫자를 리스트에 추가
        // 현재 숫자의 마지막 자릿수보다 작은 숫자들로 새로운 감소하는 숫자 생성
        for (int i = 0; i < num % 10; i++) {
            bp((num * 10) + i, idx + 1); // 자릿수를 늘려가며 감소하는 숫자 생성
        }
    }
}