9935번: EKSPLOZIJA

https://www.acmicpc.net/problem/9935

스택에 Mirko의 문자를 하나씩 넣어보면서 마지막 부분이 폭발 문자열이면 해당 문자들을 제거한다.

아래 소스의 시간복잡도는 $O(l_tl_p)$

#include<cstdio>
#include<cstring>
int n, l;
char t[1000001], p[37], s[1000001];
int main() {
    scanf("%s%s", t, p);
    l = strlen(p);
    for (int i = 0; t[i]; i++) {
        s[n++] = t[i];
        if (n >= l &&!strncmp(s + n - l, p, l)) n -= l;
    }
    s[n] = 0;
    puts(n ? s : "FRULA");
    return 0;
}

2800번: ZAGRADE

https://www.acmicpc.net/problem/2800


$O(ln2^n)$

stack으로 괄호쌍을 찾아준 다음, 비트마스크를 이용해 가능한 모든 문자열을 구하고 사전순 정렬한다.

#include<iostream>
#include<string>
#include<set>
using namespace std;
string s;
int cnt, stk[10], top;
pair<int, int> p[10];
set<string> st;
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') p[stk[top++] = cnt++].first = i;
        if (s[i] == ')') p[stk[--top]].second = i;
    }
    for (int i = 1 << cnt; --i;) {
        int ck[200] = {};
        for (int j = 0; j < cnt; j++) if (i & 1 << j) ck[p[j].first] = ck[p[j].second] = 1;
        string r;
        for (int j = 0; j < s.size(); j++) if (!ck[j]) r += s[j];
        st.insert(r);
    }
    for (auto it : st) cout << it << endl;
    return 0;
}

9012번: 괄호

https://www.acmicpc.net/problem/9012

$O(nl)$

스택에 '('이 나오면 push, ')'이 나오면 pop을 한다. 스택이 비었을 때 pop명령을 수행해야했거나 모든 괄호를 처리했을 때 스택이 비어있지 않으면 "NO"를 출력하고 아니면 "YES"를 출력한다.

#include<cstdio>
int n;
char s[51];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        int c = 0;
        for (int j = 0; s[j] && c >= 0; j++) s[j] == '(' ? c++ : c--;
        puts(c ? "NO" : "YES");
    }
    return 0;
}

10828번: 스택

https://www.acmicpc.net/problem/10828

$O(n)$

#include<cstdio>
int stk[10000], top, n;
char s[6];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%s", s);
        if (s[0] == 'p' && s[1] == 'u') scanf("%d", &x), stk[top++] = x;
        else if (s[0] == 'p') printf("%d\n", top ? stk[--top] : -1);
        else if (s[0] == 's') printf("%d\n", top);
        else if (s[0] == 'e') printf("%d\n", !top);
        else printf("%d\n", top ? stk[top - 1] : -1);
    }
    return 0;
}