Notes

감소하는 수

10 min read

25.09.12 젬미니한테 코드 작성 부탁함 네, 안녕하세요! 백준 온라인 저지 1038번 ‘감소하는 수’ 문제의 자바(Java) 풀이를 자세한 주석과 함께 설명해 드리겠습니다.

1. 문제 분석 및 핵심 아이디어

감소하는 수란?

  • 문제에서 정의한 “감소하는 수”는 각 자릿수가 왼쪽에서 오른쪽으로 갈수록 엄격하게 작아지는 수를 의미합니다.
  • 예시: 321, 950, 5, 0
  • 아닌 예시: 322 (2가 반복됨), 123 (증가함)

문제의 목표

  • N이 주어졌을 때, 0번째부터 시작하는 N번째 감소하는 수를 찾는 것입니다.
  • 만약 N번째 감소하는 수가 존재하지 않으면 -1을 출력합니다.

핵심 아이디어

  1. 단순 반복의 한계: 0부터 모든 수를 하나씩 검사하며 감소하는 수인지 확인하는 방법(브루트포스)은 비효율적입니다. N이 커지면 찾아야 할 수도 매우 커져서 시간 초과가 발생합니다. 예를 들어, 1,000,000번째 감소하는 수를 찾기 위해 수억, 수십억 개의 숫자를 검사해야 할 수도 있습니다.

  2. 생성의 관점: 모든 수를 검사하는 대신, 감소하는 수만 직접 생성하는 방법을 생각할 수 있습니다.

    • 감소하는 수는 어떻게 만들 수 있을까요?
    • 기존 감소하는 수의 마지막 자릿수보다 더 작은 숫자를 뒤에 붙이면 새로운 감소하는 수를 만들 수 있습니다.
    • 예: 32는 감소하는 수입니다. 마지막 자릿수는 2입니다. 2보다 작은 0, 1을 뒤에 붙여 320, 321이라는 새로운 감소하는 수를 만들 수 있습니다.

  3. 재귀(DFS) 또는 BFS 활용: 이 생성 과정은 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)으로 구현하기에 아주 적합합니다. 한 자리 수(0~9)에서 시작하여 점차 자릿수를 늘려가며 모든 감소하는 수를 생성할 수 있습니다.

  4. 감소하는 수의 개수는 유한하다:

    • 감소하는 수는 0~9까지의 숫자를 중복 없이 사용해서 만듭니다. (예: 321은 {1, 2, 3} 집합으로 만듦)
    • 가장 큰 감소하는 수는 9, 8, 7, 6, 5, 4, 3, 2, 1, 0을 모두 사용한 9876543210 입니다.
    • 총 감소하는 수의 개수는 10개의 숫자(0~9)로 만들 수 있는 모든 부분집합의 개수(공집합 제외)와 같습니다. 즉, 2^10 - 1 = 1023개 입니다.
    • 따라서 0번째부터 시작하면 1022번째 감소하는 수(9876543210)가 마지막입니다. 만약 N > 1022 이면 답은 무조건 -1이 됩니다. 이 사실을 이용하면 불필요한 계산을 줄일 수 있습니다.

2. 알고리즘 설계 (DFS 방식)

  1. 모든 감소하는 수를 저장할 ArrayList<Long>을 준비합니다. (long 타입을 사용하는 이유는 가장 큰 감소하는 수가 Integer 범위를 초과하기 때문입니다.)
  2. 재귀 함수 generate(long number)를 만듭니다.
    • 함수가 호출되면, 현재 number를 리스트에 추가합니다.
    • 현재 number의 마지막 자릿수를 구합니다.
    • 0부터 (마지막 자릿수 - 1)까지의 숫자를 현재 number 뒤에 붙여 새로운 수를 만듭니다.
    • 만들어진 새로운 수에 대해 generate() 함수를 재귀적으로 호출합니다.
  3. 메인 로직에서는 한 자리 수인 0부터 9까지를 시작으로 generate() 함수를 각각 호출하여 모든 감소하는 수를 생성합니다.
  4. 모든 수가 생성된 후, 리스트를 오름차순으로 정렬합니다. (재귀 호출 순서가 수의 크기 순서가 아니기 때문입니다.)
  5. 정렬된 리스트에서 N번째 인덱스의 값을 찾아 출력합니다. 만약 N이 리스트의 크기보다 크거나 같다면, 해당하는 수가 없으므로 -1을 출력합니다.

3. Java 전체 코드 (자세한 주석 포함)

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

/**
 * 백준 1038번: 감소하는 수
 * https://www.acmicpc.net/problem/1038
 */
public class Main {

    // 생성된 모든 감소하는 수를 저장할 리스트 (static으로 선언하여 재귀함수에서 쉽게 접근)
    static ArrayList<Long> list;

    public static void main(String[] args) throws IOException {

        // --- 입력 처리 ---
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // --- 초기화 ---
        list = new ArrayList<>();

        // --- 예외 처리: N번째 감소하는 수가 존재할 수 없는 경우 ---
        // 감소하는 수는 총 1023개 (0부터 9876543210까지) 존재합니다.
        // 인덱스는 0부터 시작하므로, 1022번째가 마지막 감소하는 수입니다.
        // 따라서 N이 1022보다 크면, N번째 감소하는 수는 존재하지 않으므로 -1을 출력합니다.
        if (N > 1022) {
            System.out.println(-1);
            return;
        }

        // --- 감소하는 수 생성 (DFS) ---
        // 0부터 9까지의 수로 시작하여 감소하는 수를 재귀적으로 생성합니다.
        for (int i = 0; i < 10; i++) {
            generateNumber(i);
        }

        // --- 정렬 ---
        // 생성된 수들이 순서대로 리스트에 추가되지 않았으므로, 오름차순으로 정렬합니다.
        // 예: generate(2)가 generate(10)보다 먼저 호출되므로, 2, 21, 210, 20... 순으로 리스트에 추가될 수 있습니다.
        Collections.sort(list);

        // --- 출력 ---
        // 정렬된 리스트에서 N번째 인덱스에 있는 값을 출력합니다.
        System.out.println(list.get(N));
    }

    /**
     * 감소하는 수를 생성하는 재귀 함수 (DFS 방식)
     * @param num 현재까지 만들어진 감소하는 수
     */
    public static void generateNumber(long num) {
        // 1. 현재 수를 리스트에 추가합니다.
        list.add(num);

        // 2. 현재 수의 마지막 자릿수를 구합니다. (예: 32 -> 2)
        long lastDigit = num % 10;

        // 3. 마지막 자릿수보다 작은 수를 뒤에 붙여 새로운 감소하는 수를 만듭니다.
        // 예: num이 32라면, lastDigit은 2. 2보다 작은 0, 1을 순서대로 뒤에 붙여 320, 321을 생성합니다.
        for (int i = 0; i < lastDigit; i++) {
            // 새로운 수 생성: (현재 수 * 10) + 다음 자릿수
            // 예: 32 * 10 + 1 = 321
            long newNum = (num * 10) + i;
            
            // 만들어진 새로운 수를 기준으로 재귀 호출을 통해 계속해서 다음 감소하는 수를 생성합니다.
            generateNumber(newNum);
        }
    }
}

재재출한 코드

import java.io.*;
import java.util.*;
class Main{
    static int n;
    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());
        //0 1 2 3 4 5
        //6 7 8 9 10
        //20 21 30 31 32 40
        //40 41 42(18번째) 43 50 
        
        //감소하는 수는 총 1023 0~9876543210
        //index는 0부터니까 1022가 마지막 감소하는 수
        if(n > 1022) {
            System.out.print(-1);
            return;
        }

        //반복하는 수 재귀로 생성한다.
        for(int i=0;i<10;i++){
             dfs(i);
        }

        Collections.sort(list);
        System.out.print(list.get(n));
    
    }

    static void dfs(long num){
        list.add(num);

        //현재 수의 마지막 자릿수(예: 32 -> 2)
        long lastDigit = num % 10;

        //마지막 자리수보다 작은 수를 뒤에 붙여 감소하는 수 새로 만든다.
        //32라면 lastDigit = 2이므로 2보다 작은 1,0을 뒤에 붙여 320, 321 을 생성한다.
        for(int i=0 ; lastDigit>i;i++){
            //32 * 10 + 1 = 321
            long newNum = (num * 10) + i;

            dfs(newNum);
        }
    }
}

Graph View