[BOJ] 3986_좋은 단어.cpp

# 생각

좋은 단어인지 아닌지 판별을 해야하는데 어떤 자료구조를 쓰면 좋을 것인지를 생각해야 한다

 

Stack을 쓰게 되면 LIFO의 구조를 가지고 있기 때문에

top의 원소가 지금 들어올 원소와 같다면 pop으로 삭제 시켜주면 같은 글자끼리 쌍을 지을 수 있다

 

위 방법을 반복하고 마지막에 남은 원소가 없다면 좋은단어이고

남은 원소가 있다면 좋은단어가 아님을 판별할 수 있다

 

 

# 전체 코드

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

void fastIO() { ios::sync_with_stdio(false); cin.tie(nullptr); }

int main()
{
	fastIO();
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		string tmp;
		cin >> tmp;
		stack<char> s;
		int tsz = tmp.size();
		for (int j = 0; j < tsz; j++)
		{
			if (!s.empty() and s.top() == tmp[j])
			{
				s.pop();
			}
			else
			{
				s.push(tmp[j]);
			}
		}
		if (s.size() == 0)
		{
			ans++;
		}
	}
	cout << ans;
}

 

---

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