[Programmers] 괄호 변환(Lv.2)

풀이 소요시간 : 60분

언뜻 보기 간단한 구현이였지만, 뭔가 문자열 + 재귀 조합을 풀어본적이 없어서 익숙하지 않은 구현이였다. 다 풀고나서 정석 풀이과정을 참고하여 다소 지저분했던 구현을 리팩토링했다.

분리 불가능한 균형잡힌 괄호 문자열 만드는 방법

일단 문자열을 U, V 로 나누게 되는데, 이 과정에서 나는 문자열을 뒤에서부터 역탐색하여 가장 작은 V 를 만드는데 집중했고 V가 균형잡힌 괄호 문자열이 될 때마다 U를 같이 체크하는 방식으로 구현했다. 물론 이 역시 틀린 방법은 아니지만 더욱 깔끔한 방식이 존재했다.

결국은 가장 작은 길이의 균형잡힌 괄호 문자열이 U 라는 것이다. 따라서 내가 굳이 함수에 분리가 가능한지 불가능한지를 체크하는 과정을 넣지 않고 V 가 아니라 U 의 길이를 늘려가며 균형잡힌 괄호 문자열이 되는지를 그저 체크만 하면 되는 것이였다.

길이를 1씩 증가시킬 필요도 없었다. 괄호의 특성상 2씩 증가시키는 방법이 더 현명했다.

전체 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;


//균형잡힌 괄호 문자열 여부 확인
bool Check_Count(string str)
{
    int cnt_1 = 0;
    int cnt_2 = 0;
    
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] == '(') cnt_1++;
        else if(str[i] == ')') cnt_2++;
    }
    
    return (cnt_1 == cnt_2);
}

//올바른 괄호 문자열 여부 확인
bool Check_Shape(string str)
{
    stack<char> Stack;
    
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] == '(') 
        {
            Stack.push(str[i]);
        }
        else if(str[i] == ')')
        {
            if(Stack.size() == 0) return false;
            
            Stack.pop();
        }
    }
    
    if(Stack.size() > 0) return false;
    else return true;
}

//괄호 뒤집기
string Reverse(string str)
{
    string Ans = "";
    
    for(int i = 0; i < str.length(); i++)
    {
        if(str[i] == '(') Ans += ")";
        else Ans += "(";
    }
    
    return Ans;
}

string Recursion(string str)
{
    if(str == "")
    {
        return "";
    }
    
    if(Check_Shape(str) == true)
    {
        return str;
    }
    
    int ret = 2;
    string U = str.substr(0, ret);
    string V = str.substr(ret);
    
    while(Check_Count(U) == false)
    {
        ret += 2;
        U = str.substr(0, ret);
        V = str.substr(ret);
    }
    //이 반복문을 탈출하면, U 는 최소길이 균형잡힌 괄호 문자열이다.
    
    if(Check_Shape(U) == true)
    {
        return U + Recursion(V);
    }
    else
    {
        string N = "(" + Recursion(V) + ")";
        string reverse_U = Reverse(U.substr(1, U.length() - 2));
        return N + reverse_U;
    }
    
}

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