백준 - 줄어드는 수

문제 설명

줄어드는 수 중 n번째인것을 출력하는 문제이다.

줄어드는 수를 321,950과 같은 숫자가 왼쪽에서 오른쪽으로 한자리씩 봤을 때, 작은 수여야 한다고 한다.

322와 859는 줄어드는 수가 아니라고 한다.

해당 문제는 아이디어를 잘 내야한다..

주의사항

n의 입력을 명시적으로 주고 있지만 얼만큼의 줄어드는 수를 만들어야 할지 고민일 것이다.

위 문제를 보면 줄어드는 수 중 가장 큰수는 987654321이라는 것을 알 수 있다.

TRY

선형적으로 1부터 987654321까지 String으로 변환하여 stack을 이용하여 줄어드는 수인지 판별 [시간초과]

1. 백트래킹 9876543210을 배열에 위치시켜 하나씩 골라 수를 만든다. [성공]
   • 수를 만들때 이전에 골랐던 범위는 절대 선택하지 않도록 해야한다.

풀이

public class DecresingNumber {

	private static Set<Long> answer;
	private static int[] numbers;

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

		System.out.println(solution(n));
	}

	public static long solution(int n) {
		answer = new HashSet<>();
		numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

		create(0, 0);
		List<Long> results = answer.stream()
			.sorted()
			.collect(Collectors.toList());

		if (results.size() < n) {
			return -1;
		}

		return results.get(n-1);
	}

	public static void create(int cnt, long makingNumber) {
		answer.add(makingNumber);

		if (cnt >= 10) {
			return;
		}

		create(cnt + 1, makingNumber * 10 + numbers[cnt]);
		create(cnt + 1, makingNumber);
	}
}