[백준] 3986 with C++

문제설명

---

입출력 예제

---

개념

　주어진 문자열에서 문자를 하나씩 확인하며 이전 문자와 비교를 하여 좋은 단어인지 확인하는 문제다. 입출력 예제를 분석해보면 다음과 같다. 

 

---

풀이

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	int num;
	cin >> num;
	int cnt = 0;

　입력 받을 단어의 개수를 num으로 초기화하고, 좋은 단어의 개수를 초기화할 변수 cnt를 선언한다.

 

	for (int i = 0; i < num; i++)
	{
		string str;
		cin >> str;
		
		stack<char> input;

　좋은 단어인지 확인할 문자열을 str로 초기화한다. 그리고 이 문제의 핵심인데, 문자를 하나씩 확인하며 이전 문자와 비교하여 최종적으로 좋은 단어인지 확인할 때 사용할 변수 input을 stack 자료 구조로 초기화한다. 왜 stack을 이용하는 지는 다음 코드에서 확인하도록 하자.

 

		for (int j = 0; j < str.size(); j++)
		{
			if (!input.empty() && input.top() == str[j])
				input.pop();

			else
				input.push(str[j]);
		}

		if (input.empty())
			cnt++;
	}

	cout << cnt;
}

　문자를 하나씩 비교하는데, 이때 앞의 문자가 이전 문자와 다르면 stack에서 pop 해주고, 그렇지 않다면 문자를 push 해주자. 이런 과정을 시각적으로 확인하면 다음과 같다.

 

 

　따라서 스택이 모두 비어있으면 좋은 단어이므로 cnt의 개수를 늘려주면 된다.

 

총합본

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	int num;
	cin >> num;
	int cnt = 0;

	for (int i = 0; i < num; i++)
	{
		string str;
		cin >> str;
		
		stack<char> input;
		for (int j = 0; j < str.size(); j++)
		{
			if (!input.empty() && input.top() == str[j])
				input.pop();

			else
				input.push(str[j]);
		}

		if (input.empty())
			cnt++;
	}

	cout << cnt;
}