[백준][3986] 좋은 단어

알고리즘 문제를 풀 때, 곤란한 상황이 발생할 때가 있다.

 

문제를 잘못 이해하는 것이다.

 

그래서 처음 문제를 읽을 때 집중해서 읽는 것이 중요하다.

 

 

---

처음 문제를 보고 이해한 것은 다음과 같았다.

 

A, B 위에 있는 아치형 곡선이 겹치지 않으면 좋은 단어다.

 

그러나, 진짜 문제는 다음과 같았다.

 

A, B 를 짝지었을 때, 곡선이 겹치지 않고 짝이 지어지면 좋은 단어다.

 

즉, 짝이 지어져야 한다는 것을 간과했었다.

 

 

---

 

다음과 같이 구현할 수 있다.

#include <iostream>
#include <deque>
#include <cstring>

#define input_size 100000 + 1

using namespace std;

deque<int> st;

char input[input_size];
int n;

int main()
{
	cin >> n;
	int cnt = 0;
	
	for (int i=0; i<n; i++)
	{
		memset(input, 0, input_size);
		cin >> input;
		
		for(int j=0; j<input_size && input[j] != 0; j++)
		{
				
			char cur = input[j];
			if (!st.empty())
			{
				char prior = st.back();
				
				if (cur == prior)
				{
					st.pop_back();
				}
				else
				{
					st.push_back(cur);
				}
			}
			else
			{
				st.push_back(cur);
			}
		}
		
		// if empty, cnt++
		if (st.empty())
		{
			cnt++;
		}
		else
		{
			st.clear();
		}
		
	}
	
	cout << cnt << endl;
}