Programmers Level 2: 괄호 변환(C++)

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

코딩테스트 연습 - 괄호 변환

풀이법

1) 재귀와 구현을 적절히 섞은 Kakao스러운 문제였다.

2) [용어의 정의] 파트에 구현해야 할 부분이 상세히 적혀 있으므로, 이를 따라 간다면 쉽게 풀 수 있는 문제였다고 생각한다.

3) 들어오는 문자열 p에 대해서 for문으로 탐색하며, left와 right 값을 비교하였다. 이 둘이 같아 지는 경우가 '균형 잡힌 괄호 문자열'이 되는 경우이기에, '균형 잡힌 괄호 문자열'이 되는 순간 해당 index까지는 u로 나머지를 v로 설정하였다.

4) checkChange 함수는 u 문자열이 '올바른 괄호 문자열'인지 확인하는 함수이다. stack을 활용하여 for문을 활용하여 역순으로 값을 넣어주었다. '(' 값이 들어온다면 left라는 값을 증가시켜주었으며, ')'이 들어왔을 때는 left를 감소 시켜주었다. 만약 left가 0인데 ')' 값이 들어온다면 '올바른 괄호 문자열'이 아니기에 false를 return 시켜주었다.

 

#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

bool checkChange(string u)
{
    stack<char> st;
    for(int i=u.size()-1; i>=1;i--)
    {
        st.push(u[i]);
    }
    int left=0;
    int right=0;
    char c=u[0];
    if(c=='(')
        left++;
    else
        right++;
    while(!st.empty())
    {
        char c=st.top();
        st.pop();
        if(c=='(')
            left++;
        else if(c==')'&&left>0)
            left--;
        else if(c==')'&&left==0){
            left=-1;
            break;
        }
            
    }
    if(left==0)
        return true;
    else
        return false;
}

string solution(string p) {
    string answer = "";
    if(p.size()==0) 
        return "";
    int left=0;
    int right=0;
    string u="";
    string v="";
    for(int i=0; i<p.size();i++)
    {
        if(p[i]=='(')
            left++;
        else
            right++;
        if(left==right){
            for(int j=0; j<=i;j++)
                u+=p[j];
            if(i+1<p.size())
            {
                for(int j=i+1; j<p.size();j++)
                    v+=p[j];
            }
            else
                v="";
            break;
        }
    }
    if(checkChange(u))
    {
        answer=u+solution(v);
    }
    else
    {
        string n="";
        n+='(';
        n+=solution(v);
        n+=')';
        for(int i=1;i<u.size()-1;i++)
        {
            if(u[i]=='(')
                n+=')';
            else
                n+='(';
        }
        answer=n;
    }
    
    return answer;
}