回答日:2021年-05-20

質問する

質問リンク:https://programmers.co.kr/learn/courses/30/lessons/77886

アクセスと解析

月コードで第2四半期5月に出題された問題に挑戦した.
試験の時、問題を正しく理解できずにうろうろした.そこで提案したテストケースを通して推定した.

所与の文字列xで「110」を繰り返し抽出する.(110がなくなるまで)

抽出した「110」をある場所に入れて抽出した回数.

解析によると,テスト用例の動作は上記と同様である.上記のアルゴリズムの核心は抽出した「110」をどこに置くかであり,テストを行う際にはうまく解決されていない.
その後解説を参照して解いた.(解説リンク:https://prgms.tistory.com/57)
しかし、個人的には解説に曖昧な部分があると思います.抽出された文字列を後から見ると、最初に示す「111」の前に「110」と表記される.では、「111」がなければ、どこに置くべきか疑問になります.また、必ずしも「111」でなくても、連続して出現した1の後に、最初に出現した0の点の後ろに置くことができる.
このようなアイデアで実現しましたが、タイムアウトが発生しました.
問題を探していると、「110」の抽出中に問題があることがわかりました.
抽出過程において,与えられた文字列に「110」が現れると,「110」の置換法を用いて,この過程がO(nlogn)程度の時間的複雑さを有することを発見し,問題の制限条件は以下のようになり,完全にタイムアウトできると考えられる.

1≦sの長さ≦1000000

1≦sの各元素長≦1000000

1≦sの全元素長の和≦1000000

より良い方法を求める過程でgooglingにより,スタックを用いてO(n)時間に「110」を抽出できることが分かった.(実際の実装ではベクトルが使用されています.)

コード#コード#

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for (int i = 0; i < s.size(); i++) {
        vector<char> st;
        string str = s[i];
        int cnt = 0;
        for (int j = 0; j < str.length(); j++) {
            char ch = str[j];

            if (st.size() >= 2) {
                char a = st.back();
                st.pop_back();
                char b = st.back();
                st.pop_back();
                
                if (a == '1' && b == '1' && ch == '0') {
                    cnt++;
                    continue;
                } else {
                    st.push_back(b);
                    st.push_back(a);
                    st.push_back(ch);
                }
            } else {
                st.push_back(ch);
            }
        }

        string tmp = "";
        for (int k = 0; k < st.size(); k++) {
            tmp += st[k];
        }
        
        int idx = tmp.rfind("0") + 1;
        for (int i = 0; i < cnt; i++) {
            tmp.insert(idx, "110");
        }
        answer.push_back(tmp);
    }
    return answer;
}

結果

フィードバック

実際、「110」がなぜ連続する1の前に辞書順でリードできるのかについては、他の人の位置づけを参考にして理解することができる.時間を測り、問題を理解し、問題を実現するのに十分な実力はない.問題の理解と実施を制限する時間を練習しなければならない.

リファレンスサイト

https://ansohxxn.github.io/programmers/149/