https://www.acmicpc.net/problem/2992
백트래킹을 이용하는 방법이다.
정수 x를 구성하는 숫자들을 오름차순으로 정렬하고, 그 숫자들로 만들 수 있는 순열을 오름차순으로 생성하면서 x보다 큰 최소의 순열을 출력한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string x;
string ans;
vector<char> num;
vector<bool> is_used;
bool has_answer;
void backtracking(int cnt) {
if(cnt == x.size()) {
if(ans > x) {
has_answer = true;
cout << ans;
}
return;
}
for(int i=0; i<x.size(); i++) {
if(is_used[i]) continue;
ans += num[i];
is_used[i] = true;
backtracking(cnt+1);
if(has_answer) return;
ans.pop_back();
is_used[i] = false;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> x;
for(char c : x) num.push_back(c);
sort(num.begin(), num.end());
is_used.resize(x.size(), false);
backtracking(0);
if(!has_answer) cout << 0;
return 0;
}
정수 x를 뒤에서부터 탐색하면서 감소하는 지점을 찾는다. 정수 x를 구성하는 수 중 그 지점의 수보다 큰 것이 있으면 둘을 교환한다. 그 지점 뒤부터 오름차순으로 정렬한다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool solution(string &s) {
int n = s.size();
int i = n - 1;
while (i > 0 && s[i - 1] >= s[i]) i--;
if (i == 0) return false;
int j = n - 1;
while (s[j] <= s[i - 1]) j--;
swap(s[i - 1], s[j]);
reverse(s.begin() + i, s.end());
return true;
}
int main() {
string x;
cin >> x;
if (solution(x)) cout << x;
else cout << 0;
return 0;
}
C++의 next_permutation()
을 이용하면 쉽게 해결할 수 있다.
next_permutation()
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
string x;
cin >> x;
if (next_permutation(x.begin(), x.end())) cout << x;
else cout << 0;
return 0;
}
prev_permutation()
은 next_permutation()
과 반대로 이전 순열을 구한다.