[アルゴリズム解析]BOJ 12933アヒル

100万年以来のアルゴリズム...集中力が足りなければシルバー2も大変です^^
何時間かかるかわからない問題はBOJ 12933アヒル

BOJ 12933アヒル

アヒルの鳴き声は「ガガ」です.正しいアヒルの鳴き声は、連続して1回以上の鳴き声を出すことです.例えば、「ゴロゴロ」「ゴロゴロ」「ゴロゴロ」は正しいアヒルの鳴き声です.
英善の部屋にアヒルがいた.彼はまじめに答えすぎて、アヒルが何匹いるか忘れてしまった.
突然、英善の部屋のアヒルが鳴き始め、この鳴き声が混ざった.英善はまず泣き声を録音して、それから聞いて、全部で何羽かのアヒルがいることを明らかにしたいと思っていました.
録音された音は文字列で表すことができ、1文字はアヒルの音です.アヒルの鳴き声は続く必要はありませんが、順番は「ガガ」です.「qqackukauck」のような状況は2羽のアヒルが泣いたと言える.
英善に録音する音をあげるときは、英善の部屋のアヒルの最低数を求めるプログラムを書いてください.

にゅうしゅつりょく

[入力]
1行目は英善録音の音です.音の長さは5以上2500以下であり、「q」、「u」、「a」、「c」、「k」からなる.
[出力]
英仙の部屋のアヒルの最小数を求めるプログラムを作成してください.録音した音が正しくない場合は、-1を出力します.

私の答え

わずか数ヶ月で、しかも難易度の低い実施問題なので、簡単に近づけるように努力しているようです.実はまだそんなに早く思い出していませんが、q-u-a-c-kの順番で泣き声を出さなければならないので、まずすべての入力の開始はqで始まる必要があります.
最初の文字がqであることを確認してから、後に現れた文字を検索し、前に現れた文字の後に現れた文字が正しいかどうかを確認します.
この過程でq−u,u−a,a−c,c−k,k−qなどの<map>を用い,5対を加えて確認した.
アルゴリズム全体は入力された泣き声の前から1匹ずつ確認する過程である.探索の過程で,地図を用いて条件に合致する文字を確認し,確認した文字を確認する.
すべての文字をチェックする前に探索を繰り返しますが、出現すべきでない文字が出てくると正しくない泣き声であることが確認されるので-1に戻ります.
たとえば、1回の検索が終了した後、最後に確認した文字はkでなければなりません.そうでなければ、quackという言葉は不完全を意味しますから!
一度に「エラー」を受け取ると、すべての鳴き声が5文字q-u-a-c-k順なので、文字列の長さは5の倍数でなければならず、アヒルの鳴き声の長さは5以上でなければならず、アヒルが0匹であれば-1に戻り、通過します.

コード#コード#

#include <iostream>
#include <vector>
#include <map>

// boj 12933 오리, 구현
using namespace std;

map<char, char> nextCh;

int countDuck(string sound){

    if (sound.size() % 5 != 0) return -1;
    if (sound[0] != 'q') return -1;

    vector<bool> isChecked(sound.size(), false);
    int alive = sound.size()-1;
    int count = 0;
    
    char before = sound[0];
    isChecked[0] = true;
    int i = 1;

    while (alive>0){
        for (; i < sound.size(); ++i) {
            if (isChecked[i]) continue;

            if (nextCh[before] == sound[i]){
                isChecked[i] = true;
                alive--;
                before = sound[i];
            } else continue;
        }

        if (before == 'k'){
            count ++;
            if (alive==0) break;
            for (int j = 0; j < sound.size(); ++j) {
                if (!isChecked[j]) {
                    before = sound[j];
                    isChecked[j] = true;
                    alive--;
                    i = j+1;
                    break;
                }
            }
        } else{
            count = -1;
            break;
        }
    }

    if(count==0) count = -1;

    return count;
}

int main(){
    string sound;
    cin>>sound;

    nextCh.insert({'q','u'});
    nextCh.insert({'u','a'});
    nextCh.insert({'a','c'});
    nextCh.insert({'c','k'});
    nextCh.insert({'k','q'});

    cout<<countDuck(sound);

    return 0;
}