백준 3986번 - 좋은 단어

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

3986번: 좋은 단어

 

풀이 과정

 스택을 이용해서 풀었다. 문자를 앞에서 부터 스택에 넣는다. 이때 스택의 top과 다음번 문자가 같다면 top을 pop()해준다. 최종적으로 스택이 비어있다면 좋은 단어로 분류되고 cnt++를 수행한다.

 

느낀 점

 처음 문제를 풀 때는 스택을 떠올리지 못해 오랜 시간 고민했었다. 브루트포스와 여러 자료 구조들이 문제에 필요한 건 아닌지 생각해보고, 다양한 자료 구조 유형의 문제를 풀어볼 필요가 있다.

 

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

int n, cnt; 
stack<char> stk;
string s;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			if (!stk.empty() && stk.top() == s[j]) stk.pop();
			else stk.push(s[j]);
		}
		if (stk.empty()) cnt++;
		
		while (!stk.empty()) stk.pop();
	}
	//출력
	cout << cnt << "\n";
	return 0;
}