백준 4889번 안정적인 문자열 C++

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

괄호 관련 문제가 나오면 거의 대부분은 스택 자료구조로 푼다고 생각하면 된다.

우선 문자열에 있는 문자들을 스택에 차례로 넣기 시작한다.

차례로 넣다가 스택의 top이 '{'이고 다음으로 넣을 문자가 '}'라면 안정적인 문자열이기 때문에 pop을 해주고 문자를 넣지 않고 넘어간다. 이런 방식으로 스택을 다 채운 뒤

위에서 2개씩 빼가면서 만약 2개가 '{', '{' 이거나 '}', '}'이면 하나만 뒤집으면 안정적인 문자열이기 때문에 cnt를 1 증가시킨다. 만약 2개가 '}', '{' 라면 둘 다 뒤집어야 안정적인 문자열이기 때문에 cnt를 2 증가시킨다.

이런 방법으로 스택이 빌 때까지 반복하면 답을 구할 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	string str;
	int i = 0;
	while (true) {
		cin >> str;
		if (str[0] == '-') break;
		i++;
		int cnt = 0;
		stack<char> st;
		for (char c : str) {
			if (st.empty()) {
				st.push(c);
			}
			else {
				if (st.top() == '{' && c == '}') {
					st.pop();
				}
				else {
					st.push(c);
				}
			}
		}
		while (!st.empty()) {
			char right = st.top();
			st.pop();
			char left = st.top();
			st.pop();
			if (right == left) cnt++;
			else cnt += 2;
		}
		cout << i << ". " << cnt << "\n";
	}
};