Level 2. 괄호 변환

Level 2. 괄호 변환

 

 

카카오의 구현 문제는 뭔가 어려울 것 같으면서도, 막상 풀어보면 진짜 못 풀만 한 문제는 안 내는 것 같다.

 

코드를 작성하고 나서 어딘가에서는 오류가 발생하겠지.. 이게 될까? 하면서 제출했는데 한 번에 성공해서 신기했다.

 

#include <iostream>
#include <stack>

using namespace std;

bool is_balanced(string s)
{
    int numOpen = 0, numClose = 0;

    for (char c : s)
        numOpen += (c == '('),
        numClose += (c == ')');

    return (numOpen == numClose);
}

bool is_right(string s)
{
    stack<char> stck;
    int nOpen = 0, nClose = 0;

    for (char c : s)
    {
        nOpen += (c == '(');
        nClose += (c == ')');

        if (stck.empty() || c == '(')
            stck.emplace(c);
        else if (stck.top() == '(')
            stck.pop();
        else
            return false;
    }

    return stck.empty() && (nOpen == nClose);
}

string solution(string w)
{
    // 1
    if (w.empty())
        return w;

    // 2
    int i = 2;

    while (!is_balanced(w.substr(0, i)))
        i += 2;

    string u = w.substr(0, i), v = w.substr(i);

    // 3
    if (is_right(u))
    {
        v = solution(v);

        // 3-1
        return u + v;
    }

    // 4
    // 4-1
    string t = "(";

    // 4-2
    t += solution(v);

    // 4-3
    t += ")";

    // 4-4
    u.erase(0, 1);
    u.pop_back();
    for (char& c : u) c = (c == '(') ? ')' : '(';
    t += u;

    // 4-5
    return t;
}

 

여는 괄호와 닫는 괄호의 개수를 세거나 괄호 짝을 검사할 때 스택을 사용하지 않아도 됐다.

 

어차피 열고 닫는 두 가지 경우만 존재하기 때문에, ++과 --를 이용해 0인지 검사만 해도 된다.

 

#include <iostream>

using namespace std;

bool is_balanced(string s)
{
    int n = 0;

    for (char c : s)
        (c == '(') ? ++n : --n;

    return (n == 0);
}

bool is_right(string s)
{
    int n = 0;

    for (char c : s)
    {
        if (n == 0 || c == '(')
            ++n;
        else if (0 < n)
            --n;
        else
            return false;
    }

    return (n == 0);
}

string solution(string w)
{
    // 1
    if (w.empty())
        return w;

    // 2
    int i = 2;

    while (!is_balanced(w.substr(0, i)))
        i += 2;

    string u = w.substr(0, i), v = w.substr(i);

    // 3
    if (is_right(u))
    {
        v = solution(v);

        // 3-1
        return u + v;
    }

    // 4
    // 4-1
    string t = "(";

    // 4-2
    t += solution(v);

    // 4-3
    t += ")";

    // 4-4
    u.erase(0, 1);
    u.pop_back();
    for (char& c : u) c = (c == '(') ? ')' : '(';
    t += u;

    // 4-5
    return t;
}