[ 프로그래머스 괄호 변환 (Lv2) ] (C++)

프로그래머스의 괄호변환(Lv2) 문제이다.

[ 문제풀이 ]

1) 문제에서 "균형잡힌 괄호 문자열"과 "올바른 괄호 문자열" 크게 2종류의 문자열이 등장한다.

   "균형잡힌 괄호 문자열" 이라는 것은, '('와 ')'의 갯수가 같은 문자열이고, 이 문자열에서 괄호의 짝도 알맞게 지어진

   문자열이라면 "올바른 괄호 문자열" 이라고 한다.

   문제에서 말한대로 순서대로 차근차근 같이 진행해보자.

   1. 주어진 문자열을 2개의 "균형잡인 괄호 문자열" U V로 분리한다. 단, U는 더이상 분리할 수 없어야 한다 !

   - 먼저, U를 중점적으로 생각해보자. 왜냐하면 사실 V는 주어진 문자열에서 U를 뗀 나머지 문자열 이기 때문이다.

     그렇기 때문에 문제에서도 'V는 빈 문자열이 될 수도 있다' 라고 말을 해주었다.

     주어진 문자열을 더 이상 분리할 수 없는 "균형잡힌 괄호 문자열"로 만들어서 U에 저장을 해줘야 한다.

     그러기 위해서는, 괄호의 짝( '('와 ')' 한 세트)이 최소가 되어야 한다. 왜냐하면 더 이상 분리할 수 없게 만들어야 하기

     때문이다.

     예를 들어보자. 문자열 "()()()" 가 있다고 가정해보자. 여기서 U는 무엇일까? 바로 가장 앞에 있는 "()"가 U가 된다.

     그럼, "(())()"가 있을 때는 어떻게 될까? "(())" 가 U가 될 것이다. 왜냐하면, 균형잡힌 문자열이라는 것은

     여는 괄호와 닫는 괄호의 갯수가 같은 문자열이고, 그 문자열들 중에서도 더 이상 분리할 수 없게 만들려면

     짝의 갯수가 최소가 되도록 만들어야 하기 때문이다.

     그럼 U를 어떻게 구해야 할까 ??

     문자열의 처음부터 문자열의 끝까지 탐색을 하면서, 여는 괄호의 갯수와 ,닫는 괄호의 갯수를 따로 Count 해주는 것이다.

     그렇게 Count를 하다가 처음으로 "여는 괄호의 갯수 = 닫는 괄호의 갯수"가 되는 순간, 해당 문자열을 주어진 문자열에서

     떼오는 것이 U가 될 것이다.

   2. U가 올바른 괄호 문자열인 경우

   - U가 올바른 괄호 문자열인 경우, V에 대해서 1번 과정을 다시 실행해주면 된다.

     즉, 1번에서 계속해서 언급되었던 "주어진 문자열" 이 V가 되는 것이다. 그 V 안에서 또 다른 U와 V를 찾아내서

     똑같은 방법으로 진행하면 된다.

   3. U가 올바른 괄호 문자열이 아닌 경우

   - U가 올바른 괄호 문자열이 아닌 경우, 문제에서 말한대로 따라해보자.

     1. 빈 문자열에 첫번째 문자로 '(' 를 붙입니다.

     2. V에 대해서 1단계부터 실행합니다.

     여기까지 문자열의 상태를 보면 '(' + V가 1번과정을 진행한 결과 문자열 이 되어 있을 것이다.

     3. ')'를 붙입니다.

     4. U의 첫번째와 마지막 문자를 제거합니다.

     - U의 문자열에서, 1번 Index부터 length() - 2 까지만 떼오면 된다.

     5. 반환한다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
bool Correct_String(string S)
{
    /* 올바른 괄호 문자열 인지 판단하는 함수. */
    int Flag = 0;
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '(') Flag++;
        else Flag--;
 
        if (Flag < 0) return false;
    }
    return true;
}
 
string Parsing(string S, int Start, int End)
{
    /* 문자열의 일부를 떼오는 함수. (STL : substr) 역할 */
    /* Parsing(S, Start, End)
     * - 문자열 'S'에서 Start번 Index부터 End번 Index까지만 떼내겠습니다.
     */
    string R = "";
    for (int i = Start; i <= End; i++)
    {
        R = R + S[i];
    }
 
    return R;
}
string solution(string p)
{
    if (p.length() == 0) return "";
    string U, V, Answer;
    int Open, Close;
    Open = Close = 0;
 
    for (int i = 0; i < p.length(); i++)
    {
        if (p[i] == '(') Open++;
        else Close++;
 
        if (Open == Close)
        {
            U = Parsing(p, 0, i);
            V = Parsing(p, i + 1, p.length() - 1);
            break;
        }
    }
 
    if (Correct_String(U) == true)
    {
        Answer = Answer + U;
        Answer = Answer + solution(V);
        return Answer;
    }
    else
    {
        string Temp = "(";
        Temp = Temp + solution(V);
        Temp = Temp + ")";
        U = Parsing(U, 1, U.length() - 2);
        for (int i = 0; i < U.length(); i++)
        {
            if (U[i] == '(') Temp = Temp + ')';
            else Temp = Temp + '(';
        }
        return Temp;
    }
}