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

문제

---

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

 

입력

---

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

 

출력

---

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

 

문제 풀이

---

그리디 문제.

 

다른 스택의 쌍 문제와 같이 스택을 사용한다.

}는 짝이 없는 {가 있어야만 안정적인 문자열이 될 수 있다. 따라서 문자열의 i번째 문자가 }일 때 스택에 {가 없다면 해당 }는 {로 바꾸어야 한다. 정답을 1 증가시켜준다. 또한 {로 바꾸었으므로 {를 스택에 넣어준다.

문자열의 i번째 문자가 {인 경우 탐색 중에는 안정적인 문자열인지 확인할 방법이 없다. 문자열의 끝까지 탐색이 끝났을 때 안정적인 문자열은 모든 괄호의 짝이 맞아 스택이 비어있게 된다. 따라서 스택이 비어있지 않다면 일부 {를 }로 바꾸어 짝을 맞추어야 한다. 안정적인 문자열의 } 중 일부가 {로 바뀌었다고 봐도 무방하므로, 스택의 크기는 2의 배수이고, 이 중 반을 }로 바꾸면 된다. 정답을 스택의 크기/2만큼 증가시켜주면 된다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	string str;
	int testCaseNum = 1;
	stack<char> s;
	while (true)
	{
		int answerCount = 0;
		cin >> str;
		if (str.find('-') != string::npos)
		{
			break;
		}
		for (int i = 0; i < str.length(); i++)
		{
			if (str[i] == '{')
			{
				s.push(str[i]);
			}
			else
			{
				if (s.empty())
				{
					answerCount++;
					s.push('(');
				}
				else
				{
					s.pop();
				}
			}
		}
		answerCount += s.size() / 2;
		std::cout << testCaseNum << ". " << answerCount << "\n";
		testCaseNum++;
		while (!s.empty())
		{
			s.pop();
		}
	}
	return 0;
}