[백준 1038] 감소하는 수 - Java 문제풀이

문제 링크: xxx

 

문제

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

 

입력

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

 

출력

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

풀이

접근법

1. 완전탐색으로 접근하면 시간초과가 난다.
2. 숫자가 계속 감소하는, 순열이기 때문에 최대 9876543210이라는 숫자가 만들어진다. == 배열로 접근한다면 최대 10개의 숫자가 나오게 된다.
3. 배열의 크기(10의자리 수, 100의 자리수, ...) 를 계속 키워가면서 만약 해당 크기에 도달하면 count를 늘려준다.
4. 만약 이전 수가 5라면 그 이후에는 4부터 가능하다 => for문을 이용해서 체크해준다.
5. 만약 count가 내가 구해야하는 수의 인덱스라면 수를 만들어주는데, 이건 단순 for문을 이용하면 된다.

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int count , N;
    private static long ans;
    private static boolean finished;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N=sc.nextInt();
        // 1. 완전탐색으로 접근하면 시간초과가 난다.
        // 2. 숫자가 계속 감소하는, 순열이기 때문에 최대 9876543210이라는 숫자가 만들어진다. 
        // == 배열로 접근한다면 최대 10개의 숫자가 나오게 된다.
        int[] arr = new int[10];
        int idx = 0;
        ans = -1;
        count = -1;
        finished = false;
        // 3. 배열의 크기(10의자리 수, 100의 자리수, ...) 를 계속 키워가면서 
        // 만약 해당 크기에 도달하면 count를 늘려준다.
        for(int maxIdx = 0;maxIdx < 10;maxIdx ++) {
            recur(0, maxIdx, arr);
            if (finished) break;
        }
        System.out.println(ans);
    }
    private static void recur(int nowIdx, int maxIdx, int[] arr) {
        if (finished) return;
        if (nowIdx > maxIdx) {
            count++;
            // 5. 만약 count가 내가 구해야하는 수의 인덱스라면 수를 만들어주는데, 이건 단순 for문을 이용하면 된다.
            if (count == N) {
                finished = true;
                long num = 0;
                for(int i=0;i<=maxIdx;i++) {
                    num *= 10;
                    num += arr[i];
                }
                ans = num;
            }
            return;
        }
        for(int i=0;i<=9;i++) {
        // 4. 만약 이전 수가 5라면 그 이후에는 4부터 가능하다 => for문을 이용해서 체크해준다.
            if (nowIdx == 0 || arr[nowIdx-1] > i) {
                arr[nowIdx] = i;
                recur(nowIdx+1, maxIdx, arr);
            }
            if (finished) return;
        }

    }

}