AtCoder Beginner Contest 328 D問題 解説見ながらpythonで解く

D問題をreplace()で解いたらTLEになったため、解説を見ながらやってみた🥳

ソースコード(Python)

s=input()
stack=""
for se in s:
    stack+=se
    if stack[-3:]=="ABC":
        stack=stack[:-3]
print(stack)

解説

本家の解説はこちら

スタックというデータ構造を用いる🫙
スタックは最後に入れたものを最初に取り出すようにできている。(FIFO)
特にモジュールとかはいらなさそうなので、Python標準の文字列を使ってスタックを再現した。
3,4行目では入力した文字列sをfor文で一文字ずつスタックに代入している。

肝心なのは5,6行目。スタックの後ろ3文字を見て、もしそれが"ABC"なら削除する。

それ以降はスタックに追加して、"ABC"が出たら削除して...の繰り返し。
ややこしいところだがstack[-3:]は後ろから3文字を参照して、stack[:-3]は後ろから3文字"以外"を参照している😵‍💫

なぜreplace()だとTLEになるのか。
先頭や途中の要素を削除するとそれ以降の要素をすべて前に持ってこなければならず、計算量がかさむからと言われている。
スタックなら毎回後ろから取り出せるので計算量が少なくて済む。

通った！🍭

参考：Pythonistaなら知っておきたい計算量のはなし