Bigger is Greater
これは、辞書の順序で現在の文字列の後の文字列を求める問題です.
解題ポリシー
次の文字列を辞書順に検索するアルゴリズムは、次のとおりです.の一番後ろから次の条件を満たす文字を探します.
1.1. 現在の字の後の字の中で、現在の字より大きい最小の字を探します. で検索された文字と現在の文字の位置が入れ替わる. の前から現在までの文字はそのまま使用されており、後ろの部分を並べ替えて貼り付けています. 1.1条件を満たす文字がなければ、答えがないことを返します.
リファレンス
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm 以上の手順をコードで実現した部分が注釈部分となる.
より簡便に解くためにnext置換を用いることができる.
next permutationは、現在の文字列以来初めて発生したシーケンスを返すすべてのシーケンスを検索する関数です.
コード#コード#
https://www.hackerrank.com/challenges/bigger-is-greater/problem
解題ポリシー
次の文字列を辞書順に検索するアルゴリズムは、次のとおりです.
1.1. 現在の字の後の字の中で、現在の字より大きい最小の字を探します.
リファレンス
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
より簡便に解くためにnext置換を用いることができる.
next permutationは、現在の文字列以来初めて発生したシーケンスを返すすべてのシーケンスを検索する関数です.
コード#コード#
string biggerIsGreater(string w) {
int cnt = 0;
do{
if(cnt == 1)
return w;
cnt++;
}while(next_permutation(w.begin(), w.end()));
return "no answer";
// for(int i=w.size()-2;i>=0;i--){
// int idx = -1;
// for(int j=w.size()-1;j>i;j--){
// if(w[j] > w[i]){
// if(idx == -1)
// idx = j;
// else{
// if(w[j] < w[idx])
// idx = j;
// }
// }
// }
// if(idx == -1)
// continue;
// string ans = "";
// char tmp = w[idx];
// w[idx] = w[i];
// w[i] = tmp;
// vector<char> v;
// for(int j=0;j<w.size();j++){
// if(j <= i){
// ans += w[j];
// }else{
// v.push_back(w[j]);
// }
// }
// sort(v.begin(), v.end());
// for(int j=0;j<v.size();j++){
// ans += v[j];
// }
// return ans;
// }
// return "no answer";
}
ソースhttps://www.hackerrank.com/challenges/bigger-is-greater/problem
Reference
この問題について(Bigger is Greater), 我々は、より多くの情報をここで見つけました https://velog.io/@kms9887/해커랭크-Bigger-is-Greaterテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol