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

문제 링크: https://www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

1. 주의할 점

- 전부 한번씩 뒤집어서 비교하는 일은 하지 않도록 한다(최악: 2^2000)

 

2. 구현

- 초기에 문자열을 입력받을 때, Stack에 문자를 1개씩 넣는다. 단, {}와 같이 쌍을 이룰경우, Stack에서 제외한다

- 위의 과정을 통해 안정적이지 못한 문자열이 Stack에 있을때, 가장 위에 위치한 원소 2개씩 뺀다 (문자열의 길이가 짝수이므로 가능하다)

- 원소 2개가 서로 같다면 둘중 하나만 방향을 바꾸면 되므로 Result++한다

- 원소 2개가 같지 않다면 }{ 형태이므로 원소 2개 모두 방향을 바꿔줘야 하므로 Result+=2 한다

- Result를 출력한 이후, T++를 통해 몇 번째 TC인지 확인해준다

 

#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string str;
	int t = 1, result;
	while (1) {
		cin >> str;
		if (str[0] == '-') break;
		result = 0;
		stack<char> s;
		for (int i = 0; i < str.size(); i++) {
			char c = str[i];
			if (c == '}' && !s.empty() && s.top() == '{')
				s.pop();
			else
				s.push(c);
		}
		while (!s.empty()) {
			char c1 = s.top();
			s.pop();
			char c2 = s.top();
			s.pop();
			if (c1 == c2) result++;
			else result += 2;
		}
		cout << t << ". " << result << '\n';
		t++;
	}
	return 0;
}