백준 3986: 좋은 단어

문제 요약

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

문제 분류

• 자료 구조
• 스택

문제 풀이

[C++] 백준 9012: 괄호와 비슷한 문제이다. 단지 문자열을 순차적으로 훑으면서 스택의 top과 현재 가리키는 문자가 같으면 pop, 그렇지 않으면 해당 문자를 push해서 마지막에 스택이 비어있으면 카운트 해주면 된다.

즉, 스택이 비었을 때 착한 문자가 되는것. 그 후 초기화를 위해 스택이 빌 때까지 pop시켜주고 다음 문자열을 똑같이 해주면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

int main()
{
	stack<char> st;
	int n, cnt = 0;
	string in;
	cin >> n;
	while (n--) {
		cin >> in;
		for (auto& x : in) {
			if (st.empty()) st.push(x);
			else {
				if (x == st.top()) st.pop();
				else st.push(x);
			}
		}
		if (st.empty()) cnt++;
		while (!st.empty()) st.pop();
	}
	cout << cnt;
	return 0;
}