[G5] 백준 1038번 감소하는 수 C++ 구현

리뷰

 

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

n번째 감소하는 수를 찾는 문제

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. n값을 입력 받는다, n이 9이하일 경우 n을 출력하고, n이 1022보다 클 경우 -1을 출력하고 리턴한다.
2. 변수 cur을 9로 초기화 하고, 변수 s를 "10"으로 초기화 한다.
3. cur을 전위증가시킨 값이 n보다 작을 경우 while 루프를 수행한다.
4. 매 루프마다 s의 크기를 변수 idx에 저장하고, idx를 후위 감소 시키는 while 루프를 수행한다.
5. s의 idx가 '9'라면 변수 l을 s.size()+1로 저장한 후 s를 clear시켜준다.
6. l-1부터 0까지 순회하며 s에 i + '0'을 통해 내림차순 문자열을 만든 후 break처리해 준다.
7. 만약 idx가 0이거나 s의 idx값이 s의 idx-1값보다 2이상 작다면 s의 idx를 1만큼 증가시켜 준다.
8. idx+1부터 ~ s.size()-1까지 순회를 하며 s의 현재 인덱스를 s.size()-i+'0'-1로 저장해 준후 break처리해 준다.
9. s에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 1023번째 수부터는 감소하는 수를 찾을 수 없다.
• s의 idx가 '9'가 된 경우는 맨 앞자리가 9이면서 더 이상 감소하는 수를 만들 수 없어 자릿수를 늘려 주어야 할 때다.
• s의 idx를 증가시킬 수 있을 경우 idx뒤에 있는 숫자들을 감소하는 수 중 최저값으로 만들어 주어야 한다.

 

정답 코드

#include<iostream>
using namespace std;

int main() {
	int n;  cin >> n;
	if (n <= 9) {
		cout << n;
		return 0;
	}
	else if (n > 1022) {
		cout << -1;
		return 0;
	}

	int cur = 9;
	string s = "10";
	while (++cur < n) {
		int idx = s.size();
		while (idx--) {
			if (s[idx] == '9') {
				int l = s.size() + 1;
				s.clear();
				for (int i = l - 1; i >= 0; --i) s += i + '0';
				break;
			}
			else if (idx == 0 || s[idx] < s[idx - 1] - 1) {
				s[idx]++;
				for (int i = idx + 1; i < s.size(); ++i) {
					s[i] = s.size() - i + '0' - 1;
				}
				break;
			}
		}
	}
	cout << s;
}