[백준 4889] 안정적인 문자열 (C++)

풀이

스택에 문자열을 하나씩 집어넣으면서 괄호 쌍("{}")이 맞다면 스택을 비워주고,

아니라면 계속해서 스택에 넣어준다.

 

모든 문자열을 다 순환했을 때,

스택이 비어있다면 주어진 문자열은 모두 안정적인 문자열이다.

스택이 비어있지 않다면 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 연산을 해야 한다.

 

몇 번 손으로 쓰다 보면 규칙을 찾을 수 있다.

{ { 나 } } 는 1번 만에 안정적인 문자열을 만들 수 있지만

} { 는 2번 연산을 적용해야 안정적인 문자열을 만들 수 있다.

 

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

int main()
{
	string s;
	int n = 0;
	int cnt = 0;
	while (getline(cin, s))
	{
		if (s[0] == '-')
			break;

		n++;
		cnt = 0;
		stack<char> st;
		for (int i = 0; i < s.length(); i++)
		{
			if (!st.empty() && st.top() == '{' && s[i] == '}')
				st.pop();
			else
				st.push(s[i]);
		}

		while (!st.empty())
		{
			char c1 = st.top(); st.pop();
			char c2 = st.top(); st.pop();

			if (c1 == c2)
				cnt++;
			else
				cnt += 2;
		}

		cout << n << ". " << cnt << '\n';
	}
	return 0;
}