SRM556 Div2 Hard "LeftRightDigitsGame"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12173

訳

"Left-Right Digits Game"というゲームがある。
このゲームは１桁の数字が書かれたN枚のカードを使う。
書かれている数字は文字列digitsで与えられ、
digitsのi番目の文字はi番目のカードに書かれている数字を表す。

このゲームはまず始めに一番上のカードをめくり、テーブルの上に置く。
それから残りのカードを一枚ずつめくっていき、テーブルに置かれているカードの
左か右に置いていく。

全てのカードをテーブルに置くと、N桁の数字が出来上がる。
ただし、この数字の先頭は0以外のものになっていなければならない。
このゲームの目標は出来上がるN桁の数字をなるべく小さくすることである。

このゲームで作る事が可能な、最も小さい数字を返せ。

制約

1 <= digisの長さ <= 50
digitsの中には'0'以外の文字が１つ以上含まれている

考えた事

基本的には一番左に置かれているカードよりも小さいか等しいカードであれば、
左に置いていけばよい。
最終的に一番左のカードは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;
    }
};