[DFS 알고리즘] 괄호 변환

기출 : 2020 카카오 신입 공채 1차

 

문제를 이해할 필요도 없이 문제에 제시된 알고리즘을 그대로 구현하면 정답이 나온다

 

균형잡힌 괄호 확인함수, 올바른 괄호 확인함수를 구현한 뒤 문제를 따라가면 답이 나온다

#include<bits/stdc++.h>
using namespace std;

bool chk(string p) {
    stack<char> s;
    if (p[0] == ')') return false;
    s.push(p[0]);
    for (int i = 1;i < p.length();i++) {
        if (p[i] == '(') s.push(p[i]);
        else if (p[i] == ')') {
            if (s.size() != 0) s.pop();
            else return false;
        }
    }
    if (s.size() != 0) return false;
    else return true;
}

bool chkbal(string p) {
    int a = 0, b = 0;
    for (int i = 0;i < p.length();i++) {
        if (p[i] == '(') a++;
        else b++;
    }
    return a == b;
}


string solution(string p) {
    if (p.length() == 0) return "";
    if (chk(p)) return p;
    string u, v;
    for (int i = 1;i <= (p.length() / 2);i++) {
        u = p.substr(0, i*2);
        if (i != (p.length() / 2)) v = p.substr(i * 2);
        else v = "";
        if (chkbal(u) && chkbal(v)) break;
    }
    if (chk(u)) {
        u.append(solution(v));
        return u;
    }
    else {
        string newstr = "(";
        newstr.append(solution(v));
        newstr.append(")");
        string tmpstr = u.substr(1,u.length()-2);
        for (int i = 0;i < tmpstr.size();i++) {
            if (tmpstr[i] == '(') newstr.append(")");
            else newstr.append("(");
        }
        return newstr;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s = "()))((()";
    cout << solution(s);
    return 0;
}