2020 KAKAO BLIND RECRUITMENT - 괄호 변환(c++)

문제에서 설명한 내용 그~~대로 구현하면 되는 간단한 문제였다.

다만, 여기서 말하는 균형잡힌 문자열을 구현하는 것이 약간 헷갈릴 수 있다.

그냥 문자열을 돌면서 열린 괄호와 닫힌 괄호의 수가 같은 지점까지가 u이고 나머지 부분은 v라고 생각하면 된다.

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>
 
using namespace std;
 
bool allRight(string s){ // 올바른지 판단
    stack<char> S;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='('){
            S.push(s[i]);
        } else {
            if(S.empty()){
                return false;
            }
            if(S.top()=='('){
                S.pop();
            }
        }
    }
    
    if(S.empty()){
        return true;
    }
    
    return false;
}
 
string cal(string s){
    
    // 빈 문자열이면 그냥 반환
    if(s==""){
        return "";
    }
    
    // split
    string ans, u, v;
    bool che = false;
    int open = 0, close = 0;
    for(int i=0; i<s.size(); i++){
        if(open==close && open>0 && close>0){
            che = true;
        }
        if(che==false){
            u += s[i];
        }else{
            v += s[i];
        }
        if(s[i]=='('){
            open++;
        }else{
            close++;
        }
    }
            
    if(allRight(u)){ // 올바른
        string temp = "";
        temp += u;
        temp += cal(v);
        ans = temp;
    }else{ // 올바르지 않은
        string temp = "";
        temp += '(';
        temp += cal(v);
        temp += ')';
        for(int i=1; i<u.size()-1; i++){
            if(u[i]=='('){
                temp += ')';
            }else{
                temp += '(';
            }
        }
        ans = temp;
    }
    
    return ans;
}
 
 
string solution(string p) {
    string answer = "";
    
    if(allRight(p)){
        answer = p;
        return answer;
    }
    
    answer =  cal(p);
    
    return answer;
}