프로그래머스 - 괄호 변환 - C++

https://school.programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

string solution(string p) {
    string u = "";
    if(p=="")return "";
    // 분리
    int cnt=0;
    bool b = true;
    string v="";
    for(int i=0;i<p.length();i++)
    {
        if(p[i]=='(')cnt++;
        else cnt--;
        u+=p[i];
        if(cnt<0){b=false;}
        if(cnt==0){
            v = p.substr(i+1);
            break;
        }
    }
    string result = solution(v);
    // u가 올바른 괄호 문자열이면
    if(b)
        return u+result;
    else
    {
        string im="(";
        im+=result;
        im+=")";
        u = u.substr(1,u.length()-2);
        for(int i=0;i<u.length();i++)
        {
            if(u[i]=='(')u[i]=')';
            else u[i]='(';
        }
        return im+=u;
    }
    return "";
}

이 문제는 재귀함수를 이용해 주어진 알고리즘대로 돌아가게끔 코드를 만들어 리턴하는 문제이다. 

 

solution 함수 자체를 재귀함수로 만들어 주어진 알고리즘대로 코드를 작성했더니 통과했다. 

 

if(p=="")return "";
    // 분리
    int cnt=0;
    bool b = true;
    string v="";
    for(int i=0;i<p.length();i++)
    {
        if(p[i]=='(')cnt++;
        else cnt--;
        u+=p[i];
        if(cnt<0){b=false;}
        if(cnt==0){
            v = p.substr(i+1);
            break;
        }
    }

1. 입력이 빈문자열이면 빈문자열리턴

2. u와 v를 분리하는 과정이다. u는 균형잡힌 괄호문자열이기 때문에 cnt로 개수를 세며 0이 되었을 때 즉 짝의 개수가 맞을 때 u를 분리한다. cnt가 0이하면 올바르지 않기 때문에 b를 false로 바꿔 올바른 문자열이 아니라는 것을 표시한다. 

 

string result = solution(v);
    // u가 올바른 괄호 문자열이면
    if(b)
        return u+result;
    else
    {
        string im="(";
        im+=result;
        im+=")";
        u = u.substr(1,u.length()-2);
        for(int i=0;i<u.length();i++)
        {
            if(u[i]=='(')u[i]=')';
            else u[i]='(';
        }
        return im+=u;
    }

올바른 문자열이든 아니든 재귀적으로 v에 대해서 수행해야하기 때문에 result 에 담아놓는다. 

3. 올바른 문자열이면 결과를 u에 붙여서 리턴

4. 아니라면 주어진대로 문자열을 im에 만들어놓고 u를 바꿔 더한후 리턴