3986

 

문제 요약

 

A, B로 이루어진 단어를 이차형 곡선을 그어 쌍을 지어지면 좋은 단어이며, 이 개수를 센다.

 

입력

 

N개의 단어수 ( 100이하의 자연수)

 

N개의 줄에 A와 B로 이루어진 단어가 한 줄에 하나씩 주어지며, 길이는 2와 100,000 사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않음.

 

 

출력

 

좋은 단어의 수 출력

 

풀이

 

stack 자료구조 문제로 문자열을 하나씩 입력받고 stack의 top 값이 들어온 입력과 같으면 top값을 pop 시키고, 그렇지 않으면 push 한다.

 

단어 반복마다 최종적으로 stack이 비어있으면 좋은 단어의 카운트를 1 증가시킨다.

 

#include <bits/stdc++.h>

using namespace std;

int n, cnt;
string str;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str;
        stack<char> stack;
        //홀수 인경우 좋은 단어가 될 수 없어.
        if(str.length() & 1) continue;

        for (const auto a: str) {
            if(!stack.empty() && stack.top() == a) stack.pop();
            else stack.push(a);
        }

        if(stack.empty()) cnt++;
    }

    cout << cnt << '\n';

    return 0;
}