백준 1038번 : 감소하는 수 자바

🧫 문제 분석

 

✔️ 출처

감소하는 수 골드 5

 

📖 문제

 

 

핵심

감소하는 수는 완전탐색 + 백트래킹 문제이다.

 

먼저 문제를 보면 321, 950 같은 수는 감소한다. 즉 각 앞 자리수보다 뒷 자리수가 더 작아야한다.

 

ex)

321이면 3보다 작은 수가 와야하고 여기서는 2 가 왔다

2보다 작은수 1이 왔다.

 

수를 생각해보면 0~9 까지 있고 나올 수 있는  감소하는 수 최대 값은

9 8 7 6 5 4 3 2 1 0 이다. (98억7654만..)

즉 10자리수까지만 탐색하면 된다는 의미이다. 

 

문제에서 주어지는 N번째 수가 무엇인지를 출력하면 된다.

예제 1번을 예시로 보자

 

0~9까지는 각 수에 대한 각 번호이다. 0 은 0번째 , 1은 1번째

그리고 10 은 10번째이고 11부터 19까지는 감소하는 수가 아닌 같거나 증가하는 수이므로 넘어간다.

20 이 11번째

21 12번째

30 13번째

31 14번째

32 15번째

40 16번째

41 17번째

42 18번째 <= 이 때의 수를 출력한다.

 

 

 

필자는 각 순서에 따른 숫자들을 리스트에 담고 get(n)하면 바로 n번째 수가 출력되게끔 로직을 짰다.

수는 StringBuilder로 하여  만들었다.

 

자릿수가 1자리 ( 0 ~ 9)

자릿수가 2자리 ( 10 ~ 99) 

... 

자릿수가 10자리 

이런식으로 반복문을 돌면서 

수를 만드는 재귀함수를 호출한다. 

 

list에 담긴 수의 size가 n을 넘어서면 get(n) 으로 출력하고 return 하여 반복문을 멈춘다. 

for문이 끝까지 돌았음에도 출력되지 않았다면 이는 불가능한 수이므로 -1을 출력한다.

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 1; i <= 10; i++) {
            // 각 자릿수를 넘겨 숫자를 생성
            recursion(i, 10);
            
            // 리스트에 담긴 수들의 개수가 n번째를 넘어섰다면
            if (list.size() > n) {
                System.out.println(list.get(n));
                return;
            }
        }

        System.out.println(-1);
    }


    private static void recursion(int depth, int pre) {
        // 만들어진 수는 리스트에 넣는다.
        if (depth == 0) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (pre > i) {
                sb.append(i); // 조건에 맞는 수는 추가
                recursion(depth - 1, i);
                sb.deleteCharAt(sb.length() - 1); // 리스트에 추가된 수는 뺀다. 
            }
        }
    }
}

 

---

 

참고 : 1022번째가 9876543210 이다. 1023번째부터는 불가능한 값이기에 -1이 출력되면된다.

 

 

❗ 오답노트 / 필요한 지식

1. 백트래킹 처음 배운 방식을 잘 익혀서 사용하는 것 같아서 뿌듯하다.