백준 4889 안정적인 문자열(c++)

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

4889번: 안정적인 문자열

<코드>

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

int main()
{
	string s;
	stack<char>st;
	int start=1;
	while(cin>>s)
	{
		int cnt=0;
		if(s[0]=='-') break;
			for(int i=0;i<s.size();i++)
			{
				if(s[i]=='{') st.push(s[i]);
				else if(s[i]=='}')
				{
					if(!st.empty() && st.top()=='{') 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+=2;
				else cnt+=1;
				
			}
			cout<<start<<"."<<' '<<cnt<<'\n';
			start++;
		}
		
		
}

스택을 이용한 괄호 검사 알고리즘으로 문제를 해결하였다.

{}인 경우에는 pop해주고 그렇지 않은 경우에 대해서 대비해야된다.

}{ 이 경우에는 원소 교환을 2번 해주어야 한다.

}}, {{ 이 경우에는 원소 교환을 1번 해주어야 한다.