괄호변환 C++

문제설명

 

"균형 잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

매개변수 설명

• p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
• 문자열 p를 이루는 '('와 ')'의 개수는 항상 같습니다.
• 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.

---

입출력 예

p                                                                                                    result

"(()())()"	"(()())()"
")("	"()"
"()))((()"	"()(())()"

입출력 예에 대한 설명

입출력 예 #1
이미 "올바른 괄호 문자열" 입니다.

입출력 예 #2

• 두 문자열 u, v로 분리합니다.
  • u = ")("
  • v = ""
• u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
  • v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
  • u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다.
  • 따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.

입출력 예 #3

• 두 문자열 u, v로 분리합니다.
  • u =  "()"
  • v =  "))((()"
• 문자열 u가 "올바른 괄호 문자열"이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
• 다시 두 문자열 u, v로 분리합니다.
  • u = "))(("
  • v = "()"
• u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
  • v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
  • u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
  • 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
• 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.

 

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

using namespace std;

bool check(string littleP)
{
    stack<char> st;
    for(int i=0; i<littleP.size(); i++)
    {
        if(littleP[i] == '(') st.push('(');
        else //닫는 괄호일때 
        {
            if(st.empty())//비어있는데 닫는 괄호 넣으려고 할때 
            {
                return false;
            }
            else
            {
                if(st.top()=='(')st.pop();
            }
        }
    }
    if(st.empty())return true;
    else return false;
}

string solution(string p) {
    string answer = "";
    string u,v;
    int cnt=0;
    if(p=="")return answer;
    
    for(int 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;
        }
    }
    
    if(check(u))//u가 올바른 괄호 문자열인 경우
    {
        return u+solution(v);
    }
    
    string tmp ="("+solution(v)+")";
    u = u.substr(1,u.length()-2);
    for(int i=0; i<u.size(); i++)
    {
        if(u[i] == '(')tmp+=')';
        else tmp+='(';
    }
    answer = tmp;
    return answer;
}

 

=> 문제에서 주어진대로 천천히 알고리즘에 따라 짜면 되는 문제입니다. 

=> 다만, 주어진 문자열이 '올바른 괄호 문자열'인 경우에 대해 별도의 함수를 만들어 확인하여야 합니다. 

=> 저는 stack을 사용하여 올바른 괄호 문자열인지 확인하였습니다. 

=> 이후 알고리즘은 문제에 주어진대로 천천히 풀면 되는 문제입니다.