[프로그래머스] 2020 KAKAO BLIND RECRUITMENT : 괄호 변환 (C++)

문제 링크 : 괄호 변환

[문제 접근]

그냥 문제에서 주어진 과정들을 차근차근 구현하면되는 간단한 문제이다.
문자열을 나누면서 다시 처음부터 수행하기 때문에 재귀를 사용해야한다.
과정에 재귀적으로 수행한다라는 힌트도 주어서 재귀를 사용해야한다는 것을 쉽게 알 수 있다.

균형잡힌 문자열 u,v로 분리할 때 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하기 때문에 w를 탐색하며 최초로 균형잡힌 괄호 문자열이 완성된 순간의 문자열이 더 이상 균형잡힌 괄호 문자열로 분리할 수 없는 문자열이 된다. 그리고 나머지 문자열을 v로 반환하면 된다.

[소스 코드]

#include <string>
#include <vector>

using namespace std;

bool check(string w) {
    int index=0;
    for(char c : w) {
        if(c=='(') {
            index++;
        } else {
            index--;
        }
        if(index<0) return false;
    }
    return true;
}

string reverse(string u) {
    string temp = "";
    for(char c : u) {
        if(c=='(') temp += ')';
        else temp += '(';
    }
    
    return temp;
}

string solve(string w) {
    if(check(w)) return w; // 올바른 괄호 문자열이거나 빈문자열이면 return
    else {
        string u="", v="";
        int index=0;
        for(int i=1 ; i<=w.size() ; i++) {
            if(w[i-1]=='(') index++;
            else index--;
            
            if(index==0) { // 최초로 균형 잡힌 문자열이 완성된 순간
                u = w.substr(0, i);
                v = w.substr(i);
                break;
            }
        }

        if(check(u)) {
            return u+solve(v);
        } else {
            string temp = "("+solve(v)+")";
            u = u.substr(1, u.size()-2);
            u = reverse(u);
            temp += u;
            
            return temp;
        }
    }
}

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