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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

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

pair<string, string> SeparateString(const string &s){
    int left = 0;
    int right = 0;
    string u = "";
    string v = "";
    
    for(int i=0; i<s.size(); i++){
        if(left > 0 && right > 0 && left == right){
            v += s[i];
        }else{
            if(s[i] == '('){
                left++;
            }else{
                right++;
            }

            u += s[i];
        }
    }
    
    return {u, v};
}

string ReverseString(const string& s){
    string reverse = "";
    
    for(int i=0; i<s.size(); i++){
        reverse += (s[i] == '(') ? ')' : '(';
    }
    
    return reverse;
}

string solution(string p) {
    if (p.empty()){
        return p;
    }
    
    auto [u, v] = SeparateString(p);
    
    if(IsCorrect(u)){
        return u + solution(v);
    }else{
        string answer = "(";
        answer += solution(v);
        answer += ")";
        answer += ReverseString(u.substr(1, u.size() -2));
        
        return answer;
    }
}

---

📝 풀이

IsCorrect 함수는 균형잡힌 괄호 문자열인지 판단하는 함수입니다.

SeparateString 함수는 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리하는 함수입니다.

ReverseString 함수는 문자열을 괄호 방향을 뒤집는 함수입니다.

 

재귀적으로 수행되어야 하는 요구 사항은 빈 문자열 반환과 u,v로 분리하는 부분입니다.

이후 분리된 문자열 u가 균형잡힌 괄호 문자열인지 판단하여 다음 요구 사항을 수행하면 됩니다.

u가 올바른 괄호 문자열이라면 3단계 과정을 수행한 후 return 합니다.

u가 올바른 괄호 문자열이 아니라면 4단계 과정을 수행한 후 return 합니다.