[AtCoder] ARC 108 B – Abbreviate Fox

2020年12月12日

問題

方針

括弧の対応の問題で良く使うスタックを使います。スタックに \( s \) の先頭から入れていき、\( s_i = o \) のとき、スタックの先頭から “xf" と積まれていたら “fox" と作ることができます。また、そう積まれていなかったらスタックを空にします。また、\( s_i \) が “f, o, x" 以外の文字列のときはスタックを空にします。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    string s;
    cin >> N >> s;
    int cnt = 0;
    stack<char> c;
    for (int i = 0; i < N; i++) {
        if (s[i] == 'f') {
            c.push(s[i]);
        } else if (s[i] == 'o') {
            c.push(s[i]);
        } else if (s[i] == 'x') {
            if (c.size() >= 2) {
                char c1 = c.top();
                c.pop();
                char c2 = c.top();
                c.pop();
                if (c1 == 'o' && c2 == 'f') {
                    cnt++;
                } else {
                    c = stack<char>();
                }
            } else {
                c = stack<char>();
            }
        } else {
            c = stack<char>();
        }
    }
    cout << N - 3 * cnt << "\n";
    return 0;
}