BOJ 1038 감소하는 수

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

문제

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

---

입력

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

---

출력

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

---

예제 입력 1

18

예제 출력 1

42

예제 입력 2

0

예제 출력 2

0

… 이하 예제 생략

---

코드

처음 문제를 봤을 때, 문제 이해는 잘 됐지만 풀이 방향을 잡는데 어려움을 겪었다.

가장 큰 감소하는 수는 9,876,543,210 이기 때문에, 1씩 더하며 검사하는 건 무조건 시간 초과가 발생할 수 밖에 없었고 다른 풀이 방법을 생각해야 했었다.

검사 범위	감소하는 수 개수
10 ~ 19	1개
20 ~ 29	2개
30 ~ 39	3개
…
90 ~ 99	9개

위와 같이 뭔가 규칙성이 있어 보였기 때문에, dp를 활용하는 문제인가 고민하기도 했었지만 범위 내에 있는 감소하는 수의 개수를 출력하는 문제가 아니기 때문에 직접 수를 증가시키며 알아내야 한다고 생각했다.

그래서 처음 구현에서는 각 자릿수를 의미하는 배열을 만들고, 재귀를 활용해서 감소하는 수를 구해나갔다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] decreasingNumber = new int[12];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        decreasingNumber[0] = -1;
        int N = Integer.parseInt(br.readLine());
        String answer = getDecreasingNumber(N);

        System.out.println(answer);
    }

    static String getDecreasingNumber(int N) {
        // N번 째 감소하는 수를 계산
        for (int i = 0; i < N; i++) {
            // 최대 감소하는 수를 넘어가면 -1 출력
            if(!increasePlaceValue(1)) {
                return "-1";
            }
        }

        // N번 째 감소하는 수를 출력
        StringBuilder result = new StringBuilder();
        result.append(decreasingNumber[1]);
        for (int i = 2; i < decreasingNumber.length && decreasingNumber[i] != 0; i++) {
            result.insert(0, decreasingNumber[i]);
        }

        return result.toString();
    }

    static boolean increasePlaceValue(int placeValue) {
        decreasingNumber[placeValue]++;

        if(decreasingNumber[placeValue + 1] == 0) {
            if(decreasingNumber[placeValue] > 9) {
                // 최대 감소하는 수보다 커질 경우 false 반환
                if(placeValue + 1 == decreasingNumber.length - 1) {
                    return false;
                }
                decreasingNumber[placeValue] = decreasingNumber[placeValue - 1] + 1;
                decreasingNumber[placeValue + 1] = decreasingNumber[placeValue] + 1;
            }
        } else if(decreasingNumber[placeValue + 1] <= decreasingNumber[placeValue]) {
            decreasingNumber[placeValue] = decreasingNumber[placeValue - 1] + 1;
            return increasePlaceValue(placeValue + 1);
        }

        return true;
    }
}

하지만, 보다시피 재귀함수 내의 조건문이 너무 중첩돼서 깔끔하지 않았다.

다른 코드들을 참고해보니, 그냥 처음부터 모든 감소하는 수를 만들어놓고 N번 째 감소하는 수를 출력하는 방식으로 풀었는데 이 경우 코드가 깔끔하게 작성돼서 다시 코드를 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

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

        // 감소하는 수를 모두 생성
        List<Long> decreasingNumbers = generateDecreasingNumbers();

        // N번째 감소하는 수 출력
        if (N >= decreasingNumbers.size()) {
            System.out.println(-1);
        } else {
            System.out.println(decreasingNumbers.get(N));
        }
    }

    static List<Long> generateDecreasingNumbers() {
        List<Long> result = new ArrayList<>();

        // 0부터 9까지의 단일 자리 수 추가
        for (int i = 0; i <= 9; i++) {
            dfs(i, i, result);
        }

        // 오름차순으로 정렬
        Collections.sort(result);

        return result;
    }

    static void dfs(long current, int lastDigit, List<Long> result) {
        result.add(current);

        // 다음 자리 수를 줄이는 방향으로 탐색
        for (int nextDigit = lastDigit - 1; nextDigit >= 0; nextDigit--) {
            dfs(current * 10 + nextDigit, nextDigit, result);
        }
    }
}