練習問題No.4辞書順最小問題(欲張り法)

要求

長さNの文字列Sが与えられ、長さNの文字列Tが構築される.最初、Tは空欄であり、その後、以下の任意の操作を繰り返した.1.Sのヘッダから1文字を削除し、Tの末尾に加算する.2.Sの末尾から1文字を削除し、Tの末尾に追加する

入力フォーマット

出力フォーマット

 T

テスト入力

ACDBCB

テスト出力

ABCBCD

問題を解く構想.

 ， 。
 ， T ， ， ， ， ， 。

コード#コード#

#include 
#include
#include
using namespace std;

int main() {
    string str;
    string str2;
    getline(cin, str);
    ostringstream is(str2);
    int size = str.length();
    int head = 0;
    int tail = size - 1;
    bool left = false;
    while ( head <= tail) {
        left = false;
        for (int i = 0; head + i <= tail; i++) {
            if (str[head + i] < str[tail - i]) {
                left = true;
                break;
            } else if (str[head + i] > str[tail - i]){
                left = false;
                break;
            }
        }
        if (left) {
            is << str[head++];
        } else {
            is << str[tail--];
        }
    }
    cout << is.str() << endl;
    return 0;
}