프로그래머스 [2020카카오공채] 괄호 변환 c++

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

코딩테스트 연습 - 괄호 변환 | 프로그래머스

문제가 복잡해 보이지만 정말 시키는 대로만 재귀로 잘 구현하면 된다. 재귀로 구현해야하는 부분도 문제에 잘 나와있다.

 

올바른 괄호 문자열인지 검사하는 부분만 스택을 이용해서 따로 구현했다.

문자열의 모든 문자들에 대해서 여는 괄호면 스택에 넣어주고 닫는 괄호면 스택에서 빼준다. 이때, 스택이 비어있다면 올바른 괄호 문자열이 아니므로 false를 바로 리턴한다.

 

문자열 검사가 끝났는데 스택에 아직 괄호가 남아있다면 그것도 올바른 괄호 문자열이 아니므로 false를 리턴한다.

위에서 false를 리턴하지 않았다면 올바른 괄호 문자열이므로 true를 리턴한다.

 

 

각 조건을 구현한 부분에 주석을 달아놨다.

#include <string>
#include <vector>
#include <stack>
using namespace std;
 
//올바른 괄호 문자열인지 검사
bool isok(string s) {
    stack<char> st;
 
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        }
        else if (c == ')') {
            if (st.empty()) {
                return false;
            }
            else {
                st.pop();
            }
        }
    }
 
    if (st.empty()) return true;
    else return false;
 
}
 
 
string seperate(string p) {
    if (p == "") return "";
 
    string u = "";
    string v = "";
    string result = "";
 
    int cnt1 = 0;
    int cnt2 = 0;
    int index = 0;
 
    //2번 조건
    for (char c : p) {
        if (c == '(') {
            cnt1++;
        }
        else {
            cnt2++;
        }
        index++;
 
        //균형잡힌 상태가 되면 바로 break(더 분리할 수 없도록);
        if (cnt1 == cnt2) break;
    }
 
    //u와 v로 나누다. 
    u += p.substr(0, index);
    v += p.substr(index);
 
 
    //3번 조건
    if (isok(u)) {
        result += u;
        result += seperate(v);
    }
    else {
        //4번 조건
 
        //4-1
        result = "(";
        //4-2
        result += seperate(v);
        //4-3
        result += ")";
 
        //4-4
        u = u.substr(1, u.size() - 2);
        int len = u.size();
        for (int i = 0; i<len; i++) {
            if (u[i] == '(') {
                result += ")";
            }
            else {
                result += "(";
            }
        }
    }
 
 
    //4-5
    return result;
 
}
 
 
string solution(string p) {
    string answer = "";
    
    //1번 조건
    if (isok(p)) return p;
 
 
    answer = seperate(p);
 
 
    return answer;
}