좋은 단어

*뒤에 나와 같은 단어가 나오면 그 다음다음 단어를 본다. (j++) -> 스택에 넣을 필요 없음 

*뒤에 다른 단어가 나오면 스택에 넣는다. (만약, ABBA 이렇게 있다면 AA는 BB를 둘러싼 형태이기 때문에 스택에는 ABB까지 봤을 때 스택에는 A만 들어가있는 상태일 것이다. 위 조건으로 BB가 사라지고 나면 마지막 단어인 A가 나왔을 때 스택에 있는 A와 일치하기 때문에 좋은 단어이다.)

*단어의 끝까지 봤을 때 스택이 비어있다면 좋은 단어, 아니라면 res--

 

#include <iostream> #include <vector> #include <stack> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res = n; for (int i = 0; i < n; i++) { string s; cin >> s; stack<char> st; bool flag = false; for (int j = 0; j < s.size(); j++) { if (j != s.size()-1 ) { if (s[j] != s[j + 1]) { if (!st.empty()) { if (st.top() == s[j]) { st.pop(); } else { st.push(s[j]); } } else { st.push(s[j]); } } else j++; } else { if (!st.empty()) { if (st.top() == s[j]) { st.pop(); } } else st.push(s[j]); } } if (st.empty()) { flag = true; } if (!flag) res--; } cout << res << '\n'; return 0; }