프로그래머스 - 괄호 변환

처음에 문제 해석이 어려웠는데 그냥 문제가 제시하는 대로 코드를 작성하면 된다.

코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
 
bool check(string s1)
{
    stack<char> st;
    for(int i=0; i<s1.size(); i++)
    {
        if (s1[i] == '(')
            st.push(s1[i]);
        else if (s1[i] == ')')
        {
            if (!st.empty())
            {
                if (st.top() == '(')
                    st.pop();
                else
                    return false;
            }
            else
                return false;
        }
    }
    if (!st.empty())
        return false;
    else
        return true;
}
 
string dfs(string w)
{
    if (w.empty())
        return "";
    int l = 0, r = 0;
    int i;
    string u = "", v = "";
    for(i=0; i<w.size(); i++)
    {
        if (w[i] == '(')
        {
            l++;
            u += w[i];
        }
        else if (w[i] == ')')
        {
            r++;
            u += w[i];
        }
        if (l != 0 && r != 0 && l == r)
            break;
    }
    v = w.substr(i+1);
    if (check(u))
        return u + dfs(v);
    else
    {
        string tmp = "";
        tmp += '(';
        tmp += dfs(v) + ")";
        u.erase(0, 1);
        u.pop_back();
        for(int i=0; i<u.size(); i++)
        {
            if (u[i] == '(') tmp += ')';
            else tmp += '(';
        }
        return tmp;
    }
}
 
string solution(string p) {
    if (check(p))
        return (p);
    return dfs(p);
}

너무 어렵게 생각하지 말고 우선 p 전체를 매개변수로 넘긴 후, 균형잡힌 문자열이 될 때 까지 문자열을 u, v로 나눈 후 나와있는 로직을 그대로 수행하면 된다. u와 v로 나누었을 때, u가 올바른 괄호 문자열이라면 v에 대해 다시 재귀적으로 올바른 괄호 문자열을 구하여 u에다가 더한 뒤 반환하라고 되어 있으므로 그대로 구현해준다.

 

u가 올바른 괄호 문자열이 아니라면, '(' + v에 대한 재귀 + ')'인 문자열을 만들고, u의 맨 앞과 맨 뒤를 제거한 뒤 괄호 방향을 뒤집은 후 u를 붙이면 된다고 하였으므로 위와 같이 구현하였다. 

 

처음에 헤맸던 이유는 매개변수로 완성될 문자열, 전체 문자열, 나뉜 문자열, 그 나머지 문자열 각각을 넘겨서 복잡해졌었는데, 결국 균형잡힌 문자열에 대한 로직을 dfs함수 안에서 처리하기 때문에 우리는 전체 문자열만 넘겨주면 된다.