3986 좋은 단어

‘좋은 단어’ 라는 조건을 만족하는 단어인지

체크하는 문제

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

괄호 문제와 유사한 문제

1. 문제

---

간단 설명

문자열이 주어지면, 이 문자열이 ‘좋은 단어’인지 확인하는 문제

좋은 단어란

다음 단어 AABB처럼 같은 글자끼리 위로 곡선을 그어 선 끼리 교차하지 않으면서,

선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면

좋은 단어 라고 함

다음 단어 ABAB처럼 위로 그은 곡선이 교차하면 좋지 못한 단어임

ABBA 선끼리 교차하지만 않으면 멀리있는 글자도 가능함

2. 문제 분석

---

필요변수

테스트 케이스 개수 N 최대 100개

문자열을 받을 string input 단어의 길이는 2와 100,000사이, 모든 단어 길이의 합은 1,000,000을 넘지 않음

정답의 개수 int result

스택을 이용하여 문제를 풀 예정 stack<char> st

알고리즘

1. 테스트케이스 개수 N 입력
2. 문자열 입력받기
3. 문자열의 각 문자를 확인한다
    3-1. 현재 문자가 스택의 탑과 같은 문자라면, 두 문자는 선을 그릴 수 있으므로 스택에서 뺀다
    3-2. 다른 문자라면, 스택에 넣는다
    - 이 과정을 반복해서 문자열의 끝까지 확인
4. 스택이 비어있다면 좋은 단어이므로, 정답의 개수에 +1을 해준다

3. 소스코드

---

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N, result = 0; 
	cin >> N;
	while (N--) {
		string input;
		cin >> input;

		stack<char> st;
		for (char ch : input) {
			if (!st.empty() && st.top() == ch) {
				st.pop();
			}
			else {
				st.push(ch);
			}
		}

		if (st.empty()) {
			result++;
		}
	}
	
	cout << result;

	return 0;
}