[2020 KAKAO BLIND RECRUITMENT] 괄호 변환

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

프로그래머스

닫힌 괄호, 열린 괄호로 이루어진 문자열이 주어졌을 때 올바른 괄호 문자열로 재귀적으로 바꾸는 함수를 작성하면 된다. 문제에서 알고리즘의 수도 코드를 제공해주기 때문에, 그대로 구현만 하면 된다!

 

 

[C++]

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

bool isitbalanced(string p)
{
    int left= 0; int right = 0;
    for(auto & ele : p)
    {
        if(ele == '(') left ++;
        if(ele == ')') right ++;
    }
    return left == right ? true : false; // 균형잡힌 문자열인지 아닌지
}

bool isitcorrect(string p)
{
    stack<char> st;
    st.push(p[0]);
    for(int i = 1 ; i < p.size(); i ++){
        char ele = p[i];
        if(st.top() == '(' && ele == ')')
        {
            st.pop();
            continue;
        }
         if(st.top() == '(' && ele == '(')
        {
            st.push(ele);
            continue;
        }
         if(st.top() == ')' && ele == '(')
        {
            st.push(ele);
            continue;
        }
         if(st.top() == ')' && ele == ')')
        {
            st.push(ele);
            continue;
        } 
    }
    
    if(st.empty())
    {
      return true; // 올바른 문자열이면 true
    }
    else
    {
      while(!st.empty()) st.pop(); // 스택이 빌때까지 팝팝
      return false;
    }
}

string tfm(string p, string u = "", string v = ""){
    if(p.empty()) return p; // 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
    // to do :  p 를 올바르게 만들기
    
    for(int i = 0 ; i < p.size(); i ++) // 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    {
        u.push_back(p[i]);
        if(isitbalanced(u))
        {
            v = p.substr(i+1);
            break;
        }
    }
    
    if(isitcorrect(u))
    {
        u += tfm(v);
        return u;
    }
    else
    {
      string temp = "("; // 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
      temp += tfm(v); // 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
      temp.push_back(')'); // ')'를 다시 붙입니다. 
      u.erase(u.begin()); u.erase(u.end()-1); //u의 첫 번째와 마지막 문자를 제거하고,
        //나머지 문자열의 괄호 방향을 뒤집어서
      string temp_u = "";
      for(auto & ele : u)
      {
          if(ele == '(')
          {
              temp_u.push_back(')');
          }
          if(ele == ')')
          {
              temp_u.push_back('(');
          }
      }
        
        
      temp += temp_u;
      return temp;
    }
}

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