[BOJ] 1038 : 감소하는 수

1038 : 감소하는 수

문제

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

입력

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

출력

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

풀이

생각할 수 있는 가장 큰 감소하는 수는 9876543210 이다.
이 수는 1022 번째 수이므로, 그 이후인 1023번째 수 부터는 모두 -1 을 출력할 것이다.

또한, 0부터 10까지의 수는 모두 감소하는 수이므로 n 이 해당 범위라면 자기 자신을 출력한다.

어떤 감소하는 수가 있을 때, 일의 자릿수보다 작은 값을 뒤에 붙이면 그 수 또한 감소하는 수가 된다.

따라서, 1 ~ 9 까지의 수를 queue 에 넣은 뒤, 차례대로 pop 을 하는 과정을 통해
감소하는 수를 계속해서 생성해주고 n 과 같을 때 반복문을 멈추면 된다.

만약, q 가 빌 때까지 n 과 같지 않다면, n 번째 감소하는 수는 없으니 -1 을 출력해준다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	if (n  <= 10)
	{
		cout << n;
		return 0;
	}
		
	long long cnt = 0;
	long long answer = -1;

	queue<long long> q;

	for (int i = 1; i <= 9; ++i)
	{
		q.push(i);
		++cnt;
	}


	while (q.size())
	{
		long long cur = q.front();
		q.pop();

		 long long digit_1 = (cur % 10);
		
		cur *= 10;

		for (int i = 0; i < digit_1; ++i)
		{
			++cnt;

			if (cnt == n)
			{
				answer = cur + i;
				break;
			}
			q.push(cur + i);
		}

		if (cnt == n)
			break;
	}

	cout << answer;
	return 0;
}