[C++] 4889번: 안정적인 문자열

링크

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

4889번: 안정적인 문자열

문제

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

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

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

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

입출력 예제

입력

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

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

출력

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

예제 입력 1 복사

}{
{}{}{}
{{{}
---

예제 출력 1 복사

1. 2
2. 0
3. 1

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int testCase = 1;

	while (true)
	{
		int count = 0;
		stack<char> data;

		string str;
		cin >> str;
		if (str[0] == '-') break;

		for (int i = 0 ; i < str.size(); i++)
		{
			if (!data.empty() && data.top() == '{' && str[i] == '}')
			{
				data.pop();
				continue;
			}

			data.push(str[i]);
		}

		int roop = data.size() / 2;
		for (int i = 0; i < roop; i++)
		{
			char temp_1, temp_2;

			temp_1 = data.top();
			data.pop();
			temp_2 = data.top();

			if (temp_1 == '}')
			{
				if (temp_2 == '}')
				{
					count++;
					data.pop();
				}
				else data.pop();
			}
			else if (temp_1 == '{')
			{
				if (temp_2 == '{')
				{
					count++;
					data.pop();
				}
				else
				{
					count += 2;
					data.pop();
				}
			}
		}

		cout << testCase << ". " << count << "\n";
		testCase++;
	}
}

풀이

• 그리디와 문자열이 사용되는 문제다. { }를 미리 제거하는 것을 우선순위로 두는 그리디 이다.
  
  
• 처음에는  ' { ' 다음에  ' } ' 가 나올 경우 안정적이므로 카운터를 올리지 않고 두 문자를 pop하고,
  ' { ' 가 나올경우 카운트 1증가 및 두 문자 pop
  
  그 다음 ' } ' 다음에 ' } ' 가 나올 경우 카운트  1 증가 및 두 문자 pop,
  ' { '가 나올 경우 두 문자를 다 바꿔야 { }가 되니까 카운트 2 증가 및 두 문자 pop 하는 형식으로
  구성하였다.
  
  
• 다만 } { { { } } } { 같이  { } 가 중첩 되어 있는 경우는 곤란하게 되므로 문자열 입력 후
  스택에 push하는 과정에서 { }가 나오는 경우 미리 pop 해서 빼버리도록 하였다.
  
  방법은 스택의 top에 있는 문자와 현재 push 하려는 문자가 { } 가 된다면 스택에서 pop하고
  push를 건너뛰는 방법을 사용하였다.
• 이렇게 구성하면 { } 안에 중첩이 되어 있어도 push 단계에서 모두 제거하고 변경이 필요한
  문자들만 남길 수 있다.