[C++로 풀이] 괄호 변환 ⭐⭐

📌 괄호 변환

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

bool isProper(string s) // "올바른 괄호 문자열"인지 판별
{
    stack<int> st;

    for(int i = 0; i < s.length(); i++)
    {
        if (s[i] == '(')
            st.push(s[i]);
        
        if (s[i] == ')')
            if (!st.empty())
                st.pop();
    }
    
    if (st.empty()) return true;
    else return false;
}

string removeAndReverse(string u)  // 4-4 의 과정
{
    u.erase(u.begin());   // u의 첫번쨰 문자 제거
    u.erase(u.end() - 1); // u의 마지막 문자 제거
    
    for(int i = 0; i < u.length(); i++) // 괄호 방향 뒤집기
    {
        if (u[i] == '(') u[i] = ')'; 
        else if (u[i] == ')') u[i] = '(';
    }
    
    return u;
}

string convert(string w)
{
    if (w == "") return w;  // 1. 빈 문자열인 경우 검사
    
    /* 2. w = u, v 로 분리. "균형잡힌 괄호 문자열" 찾자마자 break하면 그게 바로 u, 나머지는 v*/
    int openCount = 0; int closeCount = 0;
    int index = 0;
    for(int i = 0; i < w.length(); i++)
    {
        if (w[i] == '(') openCount++;
        if (w[i] == ')') closeCount++;
        
        if (openCount == closeCount) 
        {
            index = i + 1;
            break;
        }
    }
    string u = w.substr(0, index);
    string v = w.substr(index);
    
    string result = "";
    if (isProper(u)) // 3. 문자열 u가 "올바른 괄호 문자열"이라면
        result = u + convert(v); 
    else // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면
        result =  "(" + convert(v) + ")" + removeAndReverse(u);

    return result; 
}

string solution(string p) {
    string answer = convert(p);
    return answer;
}

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
    3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
    4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
    4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
    4-3. ')'를 다시 붙입니다. 
    4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
    4-5. 생성된 문자열을 반환합니다.

위 과정을 그대로 코드로 옮기면 되는 문제다! “올바른 괄호 문자열”을 판별하는 코드는 지난 포스팅에 썼던 코드를 그대로 활용했다. (이 문제에서는 (, )의 개수는 같다는 것을 보장해주었으니 카운팅은 하지 않음)

    for(int i = 0; i < u.length(); i++)
    {
        if (u[i] == '(') u[i] = ')'; 
        else if (u[i] == ')') u[i] = '(';
    }

원래는 앞서 else if가 아닌 if로 써서 틀렸다는 결과를 얻었다. 이러면 위의 if에서 )으로 바꿔주었으니 아래 if에 그대로 걸리게 되어 다시금 (로 바뀌게 되어 오답이 되버렸던 것이다. 경우에 따라 결과가 완전히 달라질 수 있으니 if - if를 쓸지 if - else if를 쓸지는 정말 신중하게 어떻게 달라질지 고민을 해보고 결정하자는 교훈을 얻었다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기