[解析アルゴリズムプール]BOJ 16719 ZOOC

今日の質問はBOJ 16719 ZOACです!
実施問題なので、難易度の高い問題のうち、最初の問題では難しい実施問題が発生する可能性があるので、Gold 5を選んで解答しました!

BOJ 16719 ZOAC

2018年12月、初スタートのZOOCオープニングを担当した勝宇は、誰よりも派手にZOOCをアピール.
前の字から一つ一つ展示するのが古臭いと思った勝宇は文字列を展示する新しいルールを考え出した!
ルールはこうです.つまり、まだ表示されていない文字のうち、追加時の文字列は辞書順に先頭に表示されます.
例えば、ZOOCを表示したい場合は、A→AC→OAC→ZOOCの順に表示することができる.
忙しい人のためにこのルールに従って出力されるプログラムを作成します.

にゅうしゅつりょく

私の答え

最初はどういう意味かと思っていたのですが、入力3を基準にiPadに丁寧に書いてみたら納得!残りの文字では、選択した文字列が出力される場合、出力される文字列が常にアルファベット順に最も速くなるように文字を選択する必要があります.
出力時に与えられる文字の順序は変わらないので、入力文字数と同じ大きさの配列vector<bool> printableで出力可能な文字をチェックし、これらの文字を文字列にまとめてvector<string> answerに入れる.
例入力3を使用してアルゴリズムを説明します.
最初に入力した「STARTLINK」では、最初に出力する文字が辞書順に上位の「A」です.
後から出力される文字を最も速く順番に保つためには、すべての文字のうち最も前の「A」が一番前に並ぶ必要があります.そのため、「A」の後の「RTLINK」で最も速い文字を選択しなければならず、これが「I」になります.
「I」を再選択すると、「I」は新たな基準点となる.同様の理由で、「I」以降の文字の中で最も速い文字を選択すると、「K」となります.新しい文字を検索するたびに、その文字位置のprintable配列値をtrueに変更し、新しい文字列で完了します.
しかし、「K」が新たな基準点となって文字を選択すると、「K」以降は文字がなくなる.このとき、「K」までが基準点となっていた「I」が再び基準点となり、「I」と「K」の間の文字の中で最も速い「N」を選択する.
このプロセスを完了するために、stack<int> flagsを使用して基準点としての文字の位置を管理し、現在flags.top()にある文字の後に新しい文字を選択できない場合、基準点はflags.pop()から新しいflags.top()に移行します.
このような過程で,コードを作成してコミットした結果,「Segfault」が出現し,修正に時間がかかった.いくら確認しても限界エラーではないようですが、繰り返し修正して初期化せずに使用した変数を初期化したのでパスしました.
変数に値が含まれていることを確認する必要があるようです.

コード#コード#

#include <iostream>
#include <vector>
#include <string>
#include <stack>

// BOJ 16719 ZOAC, 구현 골드 5
using namespace std;

void printByRule(string str){
    vector<string> answer;

    int len = str.size();
    vector<bool> printable(len, false);
    stack<int> flags;

    int start = 0;  // 출력 시작 점 찾기
    for (int i = 1; i < len; ++i) {
        if (str[start] > str[i]) start = i;
    }
    printable[start] = true;
    flags.push(start);

    int checked = 1;  // printable 처리된 문자 갯수 
    bool found = true;  // 새로운 문자를 찾았는지 
    while (checked<=len){
        if (found){  // 새로운 문자 찾았을 때만 새로운 문자열 추가 
            string ans = "";
            for (int i = 0; i < len; ++i) {
                if (printable[i]) ans += str[i];
            }
            answer.push_back(ans);
        }

        found = false;
        int next = 0;
        char min = '[';
        
        if (!flags.empty()){  // 이전까지 기준점이 남아있다면 새로운 문자 찾기 
            int last = flags.top();
            bool left = false;
            for (int i = last+1; i < len; ++i) {
                if (!printable[i] && (str[i] < min)){
                    left = true;
                    min = str[i];
                    next = i;
                }
            }

            if (left){  // last 이후로 출력할 게 남아있다면
                flags.push(next);
                printable[next] = true;
                checked++;
                found = true;
            }else{  // last 이후로 출력할게 없다면
                flags.pop();
            }
        }else{ // 기준점이 남아있지 않다면 str 앞에서부터 출력할 문자 찾기
            for (int i = 0; i < len; ++i) {
                if (!printable[i] && (str[i] < min)){
                    min = str[i];
                    next = i;
                }
            }
            flags.push(next);
            printable[next] = true;
            checked++;
            found = true;
        }
    }

    for (int i = 0; i < answer.size(); ++i) {
        cout<<answer[i]<<'\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string str;
    cin>>str;

    printByRule(str);

    return 0;
}