[카카오 코딩테스트]#2. 2020 괄호변환

https://programmers.co.kr/learn/challenges?tab=all_challenges

프로그래밍 강의 | 프로그래머스

1. 해결방법

stack을 활용하여 올바른 괄호 문자열인지 확인하고, 나머지는 문제에서 제시한 방법대로 재귀함수를 진행한다

---

2. 코드

#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
    string answer = "";

bool check(string p){
    stack<char> st;
    for(int i = 0; i < p.length(); i++){
        if(!st.empty() && p[i] == ')'){
            if(st.top() == '(') {
                st.pop();
            }else {st.push(p[i]);} 
        }else {st.push(p[i]);}
    }

    if(st.empty()) return 1;
    else return 0;
}

string check_function(string p){
    if(p == "") return "";
    string u = "";
    string v = "";
    int left = 0;
    int right = 0;
    
    if(check(p)) {return p;}
    else{
        for(int i = 0; i < p.length(); i++){
            if(p[i] == '(') left++;
            else right++;
            if(left == right) {
                u = p.substr(0,left+right);
                v = p.substr(left+right, p.length());
                
                if(check(u)){ 
                    return u + check_function(v);
                }else{
                    string temp;
                    temp += "(";
                    temp += check_function(v);
                    temp += ")";
                    string temp2 = u.substr(1, u.length()-2);
                    for(int j = 0; j < temp2.length(); j++){
                        if(temp2[j] == '(') temp += ")";
                        else temp += "(";
                    }
                    return temp;
                }
                
            }
            
        }
    }
}

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