SRM556 Div2 Hard "LeftRightDigitsGame"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12173
訳
"Left-Right Digits Game"というゲームがある。
このゲームは1桁の数字が書かれたN枚のカードを使う。
書かれている数字は文字列digitsで与えられ、
digitsのi番目の文字はi番目のカードに書かれている数字を表す。
このゲームはまず始めに一番上のカードをめくり、テーブルの上に置く。
それから残りのカードを一枚ずつめくっていき、テーブルに置かれているカードの
左か右に置いていく。
全てのカードをテーブルに置くと、N桁の数字が出来上がる。
ただし、この数字の先頭は0以外のものになっていなければならない。
このゲームの目標は出来上がるN桁の数字をなるべく小さくすることである。
このゲームで作る事が可能な、最も小さい数字を返せ。
制約
1 <= digisの長さ <= 50
digitsの中には'0'以外の文字が1つ以上含まれている
考えた事
基本的には一番左に置かれているカードよりも小さいか等しいカードであれば、
左に置いていけばよい。
最終的に一番左のカードはdigitsの中で最も小さい数字をおく必要がある(ただし0以外で)
その数字が置かれてからは0を左側に置いてはいけない。
そのような数字が複数ある場合、0を多く左側に置きたいため、
最後の最も小さいカードが置かれるまでは0を左に置いてもよいことにする。
ソースコード
class LeftRightDigitsGame { public: string minNumber(string digits){ int n = digits.size(); // 最終的に左側に置かれるべき数字の大きさと // そのインデックスを取得する int minDigit = '9'; int minIndex; for( int i = 0; i < n; i++ ){ int d = digits[i]; if( d != '0' && d <= minDigit ){ minDigit = d; minIndex = i; } } string ans = ""; for( int i = 0; i < n; i++ ){ // 既にminIndexを超えていた if( i > minIndex ){ // 右側に置く ans += digits[i]; } // minIndexだった else if( i == minIndex ){ // 左側に置く ans.insert( 0, digits.substr( i, 1 ) ); } // 左側と同じか小さかった else if( ans.length() == 0 || ans[0] >= digits[i] ){ // 左側に置く ans.insert( 0, digits.substr( i, 1 ) ); } // 左側よりも大きかった else{ // 右側に置く ans += digits[i]; } } return ans; } };