# [Silver II] 다음수 구하기 [문제 링크](https://www.acmicpc.net/problem/2697) ## 문제 설명 <p>어떤 수 A가 주어졌을 때, A의 다음수를 구하는 프로그램을 작성하시오.</p> <p>A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수 이다.</p> <p>A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때 이다.</p> <p>예를 들어 123과 321은 구성이 같다. 왜냐하면 두 수 모두 1이 1번, 2가 1번, 3이 1번 나오기 때문이다. 마찬가지로 14232와 12243도 구성이 같다.</p> <p>하지만, 14232와 14432는 구성이 같지 않다. </p> ## 입력 <p>첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 둘째 줄부터 T개 줄에는 각 테스트 케이스가 주어진다. 테스트 케이스는 한 줄로 이루어져 있으며, 수 A이다. A는 최대 80자리 자연수이다.</p> ## 출력 <p>각 테스트 케이스에 대해서, 한 줄에 하나씩 A의 다음수를 출력한다. 만약, A의 다음수가 없을 때는 BIGGEST를 출력한다.</p> ## 풀이 next_permutation 구현 문제입니다. 뒤에서부터 순서대로 보며 i-1번째 수가 i번째 수보다 작을 때, i번째 이후의 수 중 i-1번째 수보다 큰 가장 작은 수를 i-1번째 수와 스왑하고, i번째부터 끝까지 오름차순으로 정렬하는 방법으로 구현했습니다. ``` c++ #include<bits/stdc++.h> using namespace std; string s; void solve() { for(int i=s.length()-1;i>0;i--) { if(s[i-1]<s[i]) { int j=i; for(int k=j+1;k<s.length();k++) { if(s[i-1]<s[k] && s[k]<s[j]) j=k; } swap(s[i-1], s[j]); sort(s.begin()+i, s.end()); cout << s << '\n'; return; } } cout << "BIGGEST\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { cin >> s; solve(); } } ```