백준 1174(JAVA)

문제

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

1174번: 줄어드는 숫자

풀이

문제는 너무 단순한데 보자마자 쉽게 어떻게 풀지 떠오르지가 않았습니다.

구래서, 일단 제일 작은수부터 나열해보았습니다.
0
1
2
0
1
2
3
4
5
6
7
8
9
10
20
21
30
31
32
40
41
42
43
50
51
52
53
54
60
61
62
63
64
65
70
71
72
73
74
75
76
80
81
82
83
84
.,

97
98

(세자리)
210
…

(네자리)
3 2 1 0

(다섯자리)
4 3 2 1 0

(여섯자리)
5 4 3 2 1 0

…

(열자리)
9 8 7 6 5 4 3 2 1 0

(열한자리)
없음..

그러다보니 이렇게 열한자리는 줄어드는 수가 없어야 한다는걸 알게되었고 어떠한 특징을 알게되었습니다!

그 특징이 뭐냐면 2자리수를 예로들어보면

98 97 96 .... 87 86 85 ... 76 75 74 .. 를 거꾸로 하여 숫자가 나열된다는 것이죠!
이걸보고 바로 백트래킹으로 recursive함수를 이용해야겠단 생각이들면 굿!

그리고 recursive결과 데이터들을 결국 거꾸로 뒤집어야해서
스택을 이용했습니다!(뒤집기 위해서)
스택에 넣고, 다 넣으면 pop을해서 거꾸로 맵에 저장했습니다.!(저는 줄어드는 수를 맵을 통해서 저장했습니다. 맵으로 찾고자 하는 줄어드는 수의 인덱스를 통해 쉽게 데이터에 접근할수 있기 때문이죠!)

그리구 하나더! 저는 각 자리수마다 접근했습니다. 어차피 11자리 이상에는 줄어드는 수가 없으닌까 1자리부터 10자리까지 존재할수있는 줄어드는 수를 순서대로 맵에 저장하는 형식으로요!

그래서 결국 마지막에 출력하는 형식에는 맵의 사이즈보다 큰 입력이 N으로 들어오면 안되겠죠!@!@!@

코드

package training.backtracking;

//N번째로 작은 줄어드는 수..
//한자리수부터 열자리수 까지밖에 줄어드는수없음
//열한자리수부터는 줄어드는수가 없다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Main1174 {
    static Map<Integer, Long> map = new HashMap<>();
    static int N;
    static int[] result;
    static Stack<Long> stack;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for(int i = 1; i <= 10; i++){
            map.put(i, (long)(i - 1));
        }
        int start = 11;
        for(int i = 2; i <= 10; i++){
            //i : 자리수

            result = new int[i];
            stack = new Stack<>();
            recursive(i, 0, 9);

            while(!stack.isEmpty())
                map.put(start++, stack.pop());
        }
        if(N > map.size()){
            System.out.println(-1);
        }else{
            System.out.println(map.get(N));
        }
    }
    static void recursive(int M, int m, int start){
        if(m == M){
            StringBuilder sb = new StringBuilder();
            for (int i : result) {
                sb.append(i);
            }
            stack.push(Long.parseLong(sb.toString()));

            return;
        }
        for(int i = start; i >= 0; i--){
            result[m] = i;
            recursive(M, m + 1, i - 1);
        }

    }
}