괄호변환 (프로그래머스)

그저 알고리즘 요구에 맞게 재귀적으로 코딩하면 되는 문제이다. 

 

우선 위에서 제시한 알고리즘을 다음과 같이 나눠보았다. 

1 -> 재귀 함수 반환조건 설정

2 -> 받은 문자열을 u, v로 쪼개기

3, 4 -> 올바른 괄호인지, 아닌지 검사

3-1 -> 올바른 괄호일 경우 해야 할 작업

4-1 ~ 4-5 -> 올바르지 않은 괄호일 경우 해야 할 작업

 

이제 다음 목록들을 하나씩 살펴보도록 하겠다.

 

재귀함수 반환조건 설정

재귀 함수를 작성할 때 주의할 점은 어떤 상황에서도 재귀 함수가 종료될 수 있도록 return 조건을 설정하는 것이다. 이 작업을 해주지 않는다면 재귀 함수는 계속해서 똑같은 함수를 타고 들어가 무한루프에 빠지게 될 것이다. 이 조건은 알고리즘 1번("입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.")에서 이미 알려줬기 때문에 이 것을 사용하면 된다.   

 

받은 문자열을 u, v로 쪼개기

u, v를 쪼갤때 주의할 점은 u를 반드시 "균형 잡힌 괄호"여야 한다는 것이다. w문자열 전체를 순회 돌며 '(', ')'의 개수를 세면서 u 문자열에 문자를 넣어준다. 그리고 '('와 ')'의 개수가 서로 같을 때 v 문자열에 나머지 문자를 넣어주면 된다.

 

올바른 괄호인지, 아닌지 검사

이 작업은 스택을 이용하면 좀 더 편하게 검사할 수 있다. u 문자열 전체를 순회돈다. 만약 문자가 '('인 경우, 스택에 넣어준다. 만약 문자가 ')'인 경우, 스택에서 '(' 문자를 꺼내 주면 된다. 만약 '(' 일 때 스택이 비어있다면 그것은 올바르지 않은 괄호이다. 또한 u 전체를 순회한 이후 스택에 문자가 남아있다면 그것도 올바르지 않은 괄호이다.

 

올바른 괄호일 경우 해야할 작업

u와 1 ~ 3과정을 재귀적으로 거친 v를 서로 이어 붙여 리턴해야 하므로 u + 재귀 과정(v)을 리턴해 주면 된다.  

 

올바르지 않은 괄호일 경우 해야할 작업

v는 위와 똑같이 해주면 된다. u는 맨 앞, 맨 뒤 문자열을 지워준 후, 모든 괄호를 반대 방향으로 바꿔준다. 그리고 "(" + 재귀 과정(v) + ")" + 작업한(u)를 리턴해 주면 된다.

 

코드는 다음과 같다.

#include <string>
#include <stack>

using namespace std;

string change(string s)
{
    // 공백일 경우 공백 리턴
    if(s.empty()) return "";
    string u = "", v = "", t = "";
    int l_count = 0, r_count = 0;
    // 쪼개는 작업
    // 매개변수로 받은 문자열을 순회돌며
    for(const auto iter : s)
    {
        // 아직 쪼개진 u를 입력받지 않았을때
        if(u == "")
        {
            // 균형잡힌 괄호가 될때까지 임시 문자열에 넣어준다.
            (iter == ')') ? ++r_count : ++l_count;
            t += iter;
            // 균형잡힌 괄호일때 임시 문자열을 u에 대입한다.
            if(r_count == l_count) u = t;
        }
        // u를 입력받았으니, 나머지 문자열을 v에 넣어준다.
        else v += iter;
    }
    // 올바른 괄호 검사
    stack<char> st;
    bool uCheck = true;
    for(const auto iter : u)
    {
        // '('일 경우 스택에 넣어준다.
        if(iter == '(') st.push(iter);
        else 
        {
            // ')'일 경우
            // 스택이 비어있으면 올바르지 않은 괄호이므로
            // 루프를 빠져나온다.
            if(st.empty()) 
            {
                uCheck = false;
                break;
            }
            // 스택에서 ')'를 하나 뺀다
            else st.pop();     
        }
    }
    // 루프를 다 돌았는데 스택에 '('가 남아있으면 올바르지 않은 괄호이다.
    if(!st.empty()) uCheck = false;
    
    // 올바르지 않은 괄호일 경우
    if(uCheck == false)
    {
        // u에 맨 앞, 맨 뒤를 지운다.
        u.erase(u.begin());
        u.pop_back();
        // 문자의 방향을 반대로 바꾼다. 
        for(auto& iter : u) iter = (iter == '(') ? ')' : '(';
        // 알맞게 리턴한다.
        return "(" + change(v) + ")" + u;
    }
    
    // 알맞게 리턴한다.
    return u + change(v);
}

string solution(string p) {
    string answer = "";
    answer = change(p);
    return answer;
}