概要
文字列 s に対し、次のアルゴリズムを適用する。得られる t を求めよ
- t := 空文字列とする
- s が空でない間、次の処理を繰り返す
- s の長さが奇数なら、中央の一文字を t の末尾に付け足して、その文字を s から削除する
- s の長さが偶数なら、中央の隣接する二文字の内小さい方を t の末尾に付け足して、その文字を s から削除する
コード
class MiddleCode { public: string encode( string s ) { const int L = s.size(); if ( L <= 0 ) { return ""; } int pos = L / 2; if ( !( L % 2 ) ) { const int p1 = L / 2, p2 = p1 - 1; pos = s[ p1 ] < s[ p2 ] ? p1 : p2; } const string res = string( 1, s[ pos ] ); return res + encode( s.erase( pos, 1 ) ); } };