시작

일단 이문제는 문제만보면 어려운 문제일 수 있는데, 한번 자세히 보면 그렇게 생각보다 어렵진 않은 문제다. 그렇다면 한번 조건을 봐보자.

조건

1. A와 A를 잇고 B와 B를 잇지만, 엇는 도중 서로 겹치면 안된다.

이 조건을 가지고 있는데, 이 조건을 해결 하려면? Stack을 이용하면 편하게 해결이 된다는 것을 알 수 있다. 그렇다면 한번 알고리즘을 짜보자.

알고리즘

1. 입력받은 문자열을 0번부터 끝까지 확인 시킨다.
2. 그 도중 확인 하면서 Stack에 push를 하지만, 만약 스택 top의 있는 문자와 같다면 pop을 한다
3. pop을 한다음 다시 2번으로 돌아간다

이게 말로 하면 어려워 보이지만, 한번 2번을 한번 한 단계씩 적어보겠다. 예제 입력 1번의 ABAB로 예시를 들면

1. 우선 초기엔 비어 있으니 push (stack : A)
2. top을 확인하면 A지만, 현재 문자는 B니 다시 push(stack : AB)
3. top을 확인하는데 B지만, 현재문자는 A (stack : ABA)
4. top을 확인하는데 A, 현재는 B(stack : ABAB)

이런식으로 되어 ABAB는 좋은 문자는 아니라고 볼 수 있다. 그렇다면 한번 AABB를 예시를 들어보자

1. 초기는 push(stack : A)
2. top은 A, 현재는 A 같으니 pop (stack : )
3. stack에는 비었으니 push(stack : B)
4. top은 B, 현재도 B이니, pop(stack:)

이러면 AABB도 좋은 문자라는 것을 알 수 있다. 이런식으로 한번 풀어보면 되겠다.

코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	
	int a, result = 0;
	string word;
	cin >> a;
	for (int i = 0; i < a; i++) {
		cin >> word;
		stack<char> wordStack;
		for (int j = 0; j < word.size(); j++) {
			// 스택이 비었을때
			if (wordStack.empty()) {
				wordStack.push(word[j]);
				continue;
			} 
			// 만약 top에 있는 문자와 j번째의 문자와 같을 때 pop
			if (wordStack.top() == word[j]) {
				wordStack.pop();
			}
			// 아니면 push
			else {
				wordStack.push(word[j]);
			}
		}
		// 좋은 문자니 +1
		if (wordStack.empty()) {
			result++;
		}
		
	}
	cout << result;
}