C++:: 프로그래머스 < 괄호 변환 >

주어진 조건에 맞춰서 재귀 방식을 구현해 주면 되는 문제이다. 문제가 복잡해 보이지만 설명을 차분히 읽고 따라하면 쉽게 풀 수 있는 문제이다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

bool isGood(string s) {// 올바른 괄호 문자열인지 판단
    stack<char> st;
    for (auto c : s) {
        if (!st.empty() && c == ')' && st.top() == '(' ) st.pop();
        else st.push(c);
    }
    if (st.empty()) return true;
    return false;
}

string recur(string s) {
    if (s == "") return "";// 빈문자열은 빈문자열 그대로 반환
    int idx = 0, cnt = 0;
    for (;idx<s.size();idx++) {// 균형잡힌 문자열을 뽑아내기위해 인덱스 구함
        if (s[idx] == '(') cnt++;
        else cnt--;
        if (cnt == 0) break ;
    }
    string u = s.substr(0,idx+1);// 균형잡힌 괄호 문자열
    string v = s.substr(idx+1);// 그 뒤에 남은 문자열
    if (isGood(u)) return (u + recur(v));// u가 올바른 괄호 문자열 이면
	// u가 올바른 괄호 문자열이 아니면
    u.erase(u.begin()); u.erase(u.end()-1);// 앞뒤 지우고
    for (int i=0; i<u.size(); i++) {// 괄호 뒤집어 주기
        if (u[i] == '(') u[i] = ')';
        else u[i] = '(';
    }
    return ("(" + recur(v) + ")" + u);// 주어진 조건대로 리턴
}

string solution(string p) {
    return recur(p);
}