문제: https://www.acmicpc.net/problem/2697
문제
For this problem, you will write a program that takes a (possibly long) string of decimal digits, and outputs the permutation of those decimal digits that has the next larger value (as a decimal number) than the input number. For example:
123 -> 132 279134399742 -> 279134423799
It is possible that no permutation of the input digits has a larger value. For example, 987.
입력
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by up to 80 decimal digits which is the input value.
출력
For each data set there is one line of output. If there is no larger permutation of the input digits, the output should be the data set number followed by a single space, followed by the string BIGGEST. If there is a solution, the output should be the data set number, a single space and the next larger permutation of the input digits.
예제 입력
3 123 279134399742 987
예제 출력
132 279134423799 BIGGEST
힌트
출처
ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest E번
뒷자리의 숫자부터 검색하여 바꿀 수 있는 숫자가 있는지 찾는 방법으로 풀었봤습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <fstream> #include <iostream> #include <cstring> #include <climits> #include <algorithm> #include <string> #include <set> using namespace std; int main() { int cases; cin >> cases; for (int c = 0; c < cases; c++) { string str, strNum; cin >> str; strNum = str; int largest = strNum[strNum.size() - 1] - '0'; multiset<int> numbers; numbers.clear(); numbers.insert(largest); for (int i = strNum.size() - 2; i >= 0; i--) { if (strNum[i] - '0' < largest) { int replaceNumber; for (auto& num : numbers) { if (num > strNum[i] - '0') { replaceNumber = num; break; } } multiset<int>::iterator it = numbers.find(replaceNumber); numbers.erase(it); numbers.insert(strNum[i] - '0'); strNum[i] = replaceNumber + '0'; int j = i + 1; for (auto& num : numbers) { strNum[j] = num + '0'; j++; } break; } else if (largest < strNum[i] - '0') { largest = strNum[i] - '0'; } numbers.insert(strNum[i] - '0'); } if (str == strNum) cout << "BIGGEST" << endl; else cout << strNum << endl; } return 0; } | cs |
'Algorithm, Data structure > Solved Algorithmic Problem' 카테고리의 다른 글
BAEKJOON 2702 - Sixth Grade Math (0) | 2016.12.22 |
---|---|
BAEKJOON 2700 - Interior Points of Lattice Polygons (0) | 2016.12.21 |
BAEKJOON 2696 - Running Median (0) | 2016.12.13 |
BAEKJOON 2694 - Equal Sum Partitions (0) | 2016.12.12 |
BAEKJOON 2693 - Nth Largest Value (0) | 2016.12.11 |