問題概要
文字列をソートする際、文字列同士の比較には次の二種類が考えられる。
- 辞書式順序で早い方を手前にする
- 長さが短い方を手前にする
長さが相異なる文字列の配列が与えられる。この配列がどちらの基準でソートされているか求めよ。なお、どちらにも当て嵌まる場合・どちらにも当て嵌まらない場合もその旨を示せ。
解法
制約より、どちらの基準を用いても、結果の順序は一意に定まります。それぞれの基準について、与えられた配列がそれによるソート済み順序と一致するかを調べると、後は簡単な条件判定だけで解くことができます。
実装についてですが、判定部分に std::is_sorted を用いると楽に書けます。デフォルトの比較ファンクタは辞書式順序ですが、第三引数にファンクタを渡せるので、ここに無名関数オブジェクトを渡すことでどちらにも使えます。
コード
#define ALL( c ) (c).begin(), (c).end() class TwoWaysSorting { public: string sortingMethod( vector <string> stringList ) { bool lex = is_sorted( ALL( stringList ) ); bool len = is_sorted( ALL( stringList ), []( string &s, string &t ){ return s.size() < t.size(); } ); if ( lex && len ) { return "both"; } else if ( !( lex || len ) ) { return "none"; } else if ( lex ) { return "lexicographically"; } else { return "lengths"; } } };
