프로그래머스 - 2020 KAKAO BLIND RECRUITMENT괄호 변환

https://school.programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

 

재귀를 사용한 구현 문제이다. 

 

stack을 사용해 괄호가 올바른지 확인하는 것에다가 추가적인 요소를 덧붙힌 문제이다. 

 

카카오에서 요즘은 이런 문제가 안나오는거 같은데 예전엔 구현을 자주 시킨 것 같다.

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

bool check(string s){
    stack<char> stk1;
    
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '('){
            stk1.push(s[i]);
        }else{
            if(stk1.empty()) return false;
            else stk1.pop();
        }
    }
    
    if(stk1.empty()) return true;
    else return false;
}

string recusion(string p){
    if(p == "") return "";
    int left = 0; int right = 0;
    string u = "";
    string v = "";
    
    int i;
    for(i = 0; i < p.size(); i++){
        u += p[i];
        if(p[i] == '('){
            left++;
        }else{
            right++;
        }
        
        if(left == right) break;
    }
    
    for(int j = i + 1; j < p.size(); j++){
        v += p[j];
    }
    
    if(check(u)) return u + recusion(v);
    else{
        string phase4 = "";
        
        for(int k = 1; k < u.size() - 1; k++){
            if(u[k] == '('){
                phase4 += ')';
            }else{
                phase4 += '(';
            }
        }
        
        return '(' + recusion(v) + ')' + phase4;
    }
}

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