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

분류 : 구현

 

요구사항

1. 올바른 괄호 문자열 판단

2. 균형잡힌 괄호 문자열 만들기

 

풀이

문제에 조건들이 상세히 나와있고 구현이 중요한 문제이다

1. 올바른 괄호 문자열 판다

 - stack을 활용하여 '('과 ')'를 이용하여 판단

2. 균형잡힌 괄호 문자열 만드리

 - '(', ')'의 개수로 판단한다

3. 나머지는 문제에 주어진대로 백트래킹을 활용해 구현한다

 

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

string ans="";
bool check(string org){
    int cnt=0;
    if(org.size()==0)
        return true;
    stack<char> q;
    q.push(org[0]);
    for(int i=1 ; i <org.size() ; i++){
        char now = org[i];
        if(q.empty()){
            q.push(now);
        }
        else{
            char qtop = q.top();
            if(qtop ==')'){
                q.push(now);
            }
            else if(qtop=='('){
                if(now==')'){
                    q.pop();
                }
                else{
                    q.push(now);
                }
            }
        }
    }
    if(q.empty()) return true;
    else return false;
}


string dfs(string org, string a, string b){
    if(check(org))
        return org;
    if(org.empty())
        return "";
    int cntH=0;
    int cntL=0;
    string newstr;
    int cnt=0;
    for(int i=0 ; i <org.size(); i++){
        //홀수 개
        if(org[i]=='('){
            cntH++;
            newstr+=org[i];
        }
        else if(org[i]==')'){
            cntL++;
            newstr+=org[i];
        }
        if(cntH!=0 && cntL!=0){
            if(cntH == cntL){
                break;
            }
        }
        cnt++;
    }
    if(check(newstr)){
        return newstr+=dfs(org.substr(cnt+1,-1),"","");
    }
    else{
        string Nstr;
        Nstr += '('; 
        string Sstr = dfs(org.substr(cnt+1,-1),"","");
        Nstr += Sstr;
        Nstr += ')';
        auto iter =newstr.begin();
        newstr.erase(iter);
        iter=newstr.end();
        iter--;
        newstr.erase(iter);
        string nowNstr;
        for(int i=0 ; i <newstr.size(); i++){
            if(newstr[i] =='(' )
                nowNstr.push_back(')');
            else
                nowNstr.push_back('(');
        }
        Nstr+=nowNstr;
        return Nstr;
    }
}

string solution(string p) {
    string answer = "";
    answer += dfs(p,"","");
    return answer;
}

/*
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.
*/