괄호 변환[프로그래머스]

접근법:

빈 문자열 이라면 빈 문자열을 리턴한다
문자열이 있다면 균형잡힌 문자열인지 확인한다.
균형잡힌 문자열이 올바른 괄호 문자열인지 확인한다.
이미 균형잡힌 문자열이고 올바른 괄호 문자열이면 그대로 리턴한다.
올바르지않은 균형문자열이라면
1. 기록해둔 최대로 긴 균형잡힌 문자열의 위치를 토대로 문자열 u 와 v로 나눈다.
2. v를 재귀 함수를 사용해 같은 과정을 반복한다.
3. 주어진 알고리즘을 수행해 변환하고 결과물을 리턴한다.

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

string solve(const string& w)
{
    if(w.empty())
    {
        return "";
    }
    bool balanced = true;
    bool right = true;
    int numOpen = 0;
    int numClose = 0;
    int firstBalancedPosition = -1;
    bool firstRight = false;
    stack<char> st;
    for(int i = 0; i < w.size(); ++i)
    {
        if(w[i] == '(')
        {
            numOpen++;
            st.push(w[i]);
        }
        if(w[i] == ')')
        {
            numClose++;
            if(!st.empty() && st.top() == '(')
            {
                st.pop();
            } else 
            {
                st.push(w[i]);
            }
        }        
        if(firstBalancedPosition == -1 && numOpen == numClose)
        {
            firstBalancedPosition = i;
            if(st.empty()) firstRight = true;
        }
    }
    
    if(numOpen != numClose) balanced = false;
    if(balanced && !st.empty()) right = false;
    if(balanced && right) return w;
    string u = w.substr(0, firstBalancedPosition + 1);
    string v(w.begin() + firstBalancedPosition + 1, w.end());
    if(firstRight)
    {
        return u + solve(v);
    } 
    else 
    {
        string temp = "(";
        temp += solve(v);
        temp += ")";
        for(int i = 1; i < u.size() - 1; ++i)
        {
            if(u[i] == '(') temp += ')';
            else temp+= '(';
        }
        return temp;
    }
}

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

무인도 여행[프로그래머스]

수식 최대화[프로그래머스]