[Qualification Round 2017] Problem B. Tidy Numbers : https://code.google.com/codejam/contest/dashboard?c=3264486#s=p1

Tidy Numbers.cc

//
//  Created by fpdjsns on 2019. 1. 22
//  Copyright © 2019 fpdjsns. All rights reserved.
//

/*
 * 시간복잡도 : O(|N|^2)
 * 공간복잡도 : O(|N|)
 */
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		string N;
		cin >> N;
		int size = N.size();

		string answer = "";
		vector<pair<int, int>> nList(size);
		for (int i = 0; i < size; i++) {
			nList[i] = { N[i], i };
		}
		// (N[i], i) -> N[i] 오름차순 정렬
		sort(nList.begin(), nList.end());

		int i = 0;
		for (i = 0; i < size; i++) {
			answer.push_back(N[i]);
			if (nList[i].second != i) {
				for (; i + 1< size; i++) {
					// 내림차순 나오면 종료
					if (answer[i] > N[i + 1]) break;
					answer.push_back(N[i + 1]);
				}
				for (int j = i; j >= 0; j--) {
					if (j != i) answer[j + 1] = '9'; // 최대값 9로 갱신

					answer[j]--; // j번째 값 - 1
					if (answer[j] == '0' - 1) { // 0 - 1 이었다면
						answer[j] = '9'; // 9로 예외처리
					}
					else if (0 < j && answer[j - 1] <= answer[j]) { // 오름차순이면 종료
						break;
					}
				}
				break;
			}
		}
		i++;
		for (; i < size; i++) {
			answer.push_back('9'); // 이후 값들은 모두 최대값 9로 채운다.
		}

		// 가장 앞의 숫자가 0이면 삭제 처리
		if (answer[0] == '0')
			answer.erase(0,1);

		cout << "Case #" << t << ": " << answer << endl;

	}
	return 0;
}