프로그래머스 60058: 괄호 변환 (2020 카카오 공채)

#include <string>
using namespace std;

bool check(string s) { // 올바른 괄호 문자열인지 판별
	int i, cnt = 0;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == '(') cnt++;
		else cnt--;
		if (cnt < 0) return false;
	}
	return cnt == 0;
}

string solution(string p) {
	string answer = "";
	int cnt = 0, i;
	string u, v;

	if (p == "") return p; // 1단계

	// 2단계
	for (i = 0; i < p.size(); i++) {
		if (p[i] == '(') cnt++;
		else cnt--;

		if (cnt == 0) {
			u = p.substr(0, i + 1);
			v = p.substr(i + 1);
			break;
		}
	}

	// 3단계
	if (check(u)) return u + solution(v);

	// 4단계
	answer = '(' + solution(v) + ')';
	for (i = 1; i < u.size() - 1; i++) {
		answer += (u[i] == '(' ? ')' : '(');
	}
	return answer;
}