[Algorithm][JAVA] 백준 1038번: 감소하는 수

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

1038번: 감소하는 수

 

 

---

문제

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

 

입력

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

 

출력

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

 

코드

참고: https://comgong-man.tistory.com/196

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

public class Main {
	public static int N;
	public static List<Long> list;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		if (N > 1022) {
			System.out.println(-1);
			System.exit(0);
		}
		
		list = new ArrayList<Long>();
		for (int i = 0; i < 10; ++i) {
			calc(i, 1);
		}
		Collections.sort(list);
		System.out.println(list.get(N));
	}
	
	public static void calc(long num, int len) {
		if (len > 10) {
			return;
		}
		
		list.add(num);
		
		for (int i = 0; i < 10; ++i) {
			if (num % 10 > i) {
				calc((num * 10) + i, len + 1);
			}
		}
	}
}

 

오랜만에 백준을 C언어로 풀려고 하니 잘 기억이 안나서 결국 자바로 도전했다...

그러나 자바도 헷갈리는 개념들이 있어서 다시 공부한 후에 구글링을 통해 코드를 완전히 이해했다.