2020 카카오 기출 괄호 변환

https://programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

유형: 문자열 변환

• is_check()에서 stack을 활용하여 "올바른"인지 "균형잡힌" 인지 구분한다
• is_check()에서 "올바른"과 "균형잡힌"의 경계선을 구한다.
• substr을 활용하여 u,v로 나눈다

/*
	main
		입력
		ans+=solution
		출력

	solutioin w
		if 빈 문자 
			리턴
		flag = is_check w
		pos를 구했으니 u,v 알 수 있음
		if 균형이면
			tmp = ( + solution v + ) 
			u의 pop_front, pop_back
			for u의 길이
				반대로 업데이트
			tmp + 위에 반대로 업데이트한거
		return tmp

	is_check w
		int ret
		stack<char> s;
		for 문자열길이
			if '('
				푸시
				ret++
			else ')'
				if 빈공간 아닐시
					팝
				ret--;
			if ret ==0
				pos는 끊을 위치
				if s가 비었으면 
					올바른
					return true
				else
					균형
					return false
*/
#include<iostream>
#include<deque>
#include<stack>
#include<string>
using namespace std;
int pos;
bool is_check(string p)
{
	int ret = 0;
	pos = 0;
	stack<char> st;
	for (int i = 0; i < p.size(); i++)
	{
		if (p[i] == '(')
		{
			st.push('(');
			ret++;
		}
		else {
			if (!st.empty())
			{
				st.pop();
			}
			ret--;
		}
		if (ret == 0)
		{
			pos = i+1;
			if (st.empty())
			{
				return true;
			}
			else {
				return false;
			}
		}
	}
}
string solution(string p)
{
	if (p.length() == 0) return "";
	bool flag = is_check(p);
	string u = p.substr(0, pos);
	string v = p.substr(pos, p.size()-pos);
	
	if (flag)
	{
		return u+solution(v);
	}
	else
	{
		string tmp = "(" + solution(v) + ")";
		for (int i = 1; i < u.size()-1; i++)
		{
			if (u[i] == ')')
			{
				tmp += "(";
			}
			else
			{
				tmp += ")";
			}
		}
		return tmp;
	}
}
int main() {
	string p;
	cin >> p;
	string ans=solution(p);
	cout << ans;
}