알고리즘 :: 백준 :: 3986 - 좋은 단어

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

• 입력: 'A', 'B'로만 이뤄진 문자열, 길이 ≤ 100'000, 문자열 개수 N ≤ 100
• 출력: 좋은 단어 개수

✏️ 문제풀이

'교차하지 않는다', '짝을 찾는다' 같은 용어는 먼저 '스택'을 떠올립시다.

• 단어 내 문자를 하나씩 스택에 넣습니다.
• 현재 top이 가리키는 문자와 똑같은 문자라면, 위 그림과 같이 서로 사라집니다.

문자열 끝까지 탐색했는데,

• 스택이 비어있다면, 좋은 단어입니다.
• 스택이 비어있지 않다면, 좋은 단어가 아닙니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	int N;
	cin >> N;
	
	int result = 0;
	
	while (N--) {
		string word;
		cin >> word;
		
		stack<char> stk;
		
		for (char c : word) {
			if (!stk.empty() && stk.top() == c) stk.pop();
			else stk.push(c);
		}
		if (stk.empty()) result++;
	}
	cout << result;
}

 

🔗 코드 링크

🕧 결과