[AtCoder] ARC 108 B – Abbreviate Fox
問題
方針
括弧の対応の問題で良く使うスタックを使います。スタックに \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません