[백준] 24552 올바른 괄호⭐

[백준] 24552 올바른 괄호

• https://www.acmicpc.net/problem/24552

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

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

	//여는 괄호가 많은지 닫는 괄호가 많은지 확인
	//(: +1, ): -1
	int cnt = 0;
	for (int i = 0; i < S.length(); ++i) {
		if (S[i] == '(') cnt++;
		else cnt--;
	}
	//)의 개수가 더 많은 경우
	//(의 개수가 더 많도록 문자열 뒤집기
	if (cnt < 0) {
		string newS = "";
		for (int i = S.length() - 1; i>= 0; --i) {
			if (S[i] == '(') newS += ')';
			else newS += '(';
		}
		S = newS;
	}

	//올바른 괄호열이 끝나는 지점의 인덱스 구하기
	int endIdx = -1;
	int idx = 0;
	stack<char> st;
	while (idx < S.length()) {
		if (st.empty()) {
			st.push(S[idx]);
		}
		else {
			if ((st.top() == '(') && (S[idx] == ')')) st.pop();
			else st.push(S[idx]);
		}

		if (st.empty()) endIdx = idx;
		idx++;
	}
	
	//올바른 괄호열 접두사 제거
	if(endIdx != -1) S = S.substr(endIdx + 1);

	//접두사 () 제거 후 등장하는 모든 ( 정답이 될 수 있음
	//(의 개수 세기
	int answer = 0;
	for (int i = 0; i < S.length(); ++i) {
		if (S[i] == '(') answer++;
	}

	cout << answer;
	return 0;
}