[프로그래머스/C++] 괄호 변환

프로그래머스

 

 

> 위를 그대로 구현하면 됨

 

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

using namespace std;

// 올바른 문자열인지 체크
bool isCorrect(string s) {
    stack<char> str;
    for(int i = 0; i < s.size(); i++) {
        if(!str.empty() && s[i] == ')' && str.top() == '(') str.pop();
        else str.push(s[i]);
    }
    
    if(str.empty()) return true;
    return false;
}

// 괄호 변환
string convert(string s) {
	// 빈 문자열이면 빈 문자열 반환
    if (s == "") return "";
    
    // 균형잡힌 문자열을 구하기 위해 인덱스를 구함
    int idx = 0, cnt = 0;
    for(;idx < s.size(); idx++) {
        if(s[idx] == '(') cnt++;
        else cnt--;
        
        if(cnt == 0) break;
    }
    
    // 균형잡힌 문자열
    string str1 = s.substr(0, idx + 1);
    // 나머지 문자열
    string str2 = s.substr(idx + 1);
    
    // str1이 올바른 문자열일 때
    if(isCorrect(str1)) return (str1 + convert(str2));
    // str2가 올바른 문자열이 아닐 때
    else {
    	// 앞 뒤 제거
        str1.erase(str1.begin());
        str1.erase(str1.end()-1);
        
        // 괄호 뒤집기
        for(int i = 0; i < str1.size(); i++) {
            if(str1[i] == '(') str1[i] = ')';
            else str1[i] = '(';
        }
        
        // 4-1~3과 위에서 만든 올바른 문자열을 리턴
        return ("(" + convert(str2) + ")" + str1);
    }
}

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