백준) 3986 좋은 단어

좋은 단어 

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

예제 입력 

3
ABAB
AABB
ABBA

같은 글자 두 개씩 쌍을 짓는데, 글자 위로만 선을 그어서 쌍을 지어야 한다.

이 선이 겹치지 않을 때 좋은 단어로 친다.

예제의 경우에 ABAB는 좋은 단어가 아니다.

퍼뜩 떠오른 생각은 스택에 넣으면서 최상위 글자랑 지금 넣는 글자랑 다르면 좋은 단어가 아니다.

따라서 첫 글자는 무조건 스택에 넣어야 한다.

두번째 글자부터 이를 확인해 주면된다.

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
 
int n, ans, len;
char buf[100001];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        len = strlen(buf);
        stack<char> st;
        st.push(buf[0]);
 
        for (int j = 1; j < len; ++j) {
            if (st.empty())
                st.push(buf[j]);
 
            else if (st.top() == buf[j])
                st.pop();
            else
                st.push(buf[j]);
        }
 
        if (st.empty())
            ans++;
    }
    printf("%d", ans);
}