Programmers : 괄호 변환

풀이 요약

재귀, 스택

풀이 상세

1. 중요한 점은 2가지이다.

   • 올바른 괄호 문자열인지 확인 할 수 있어야 한다.
   • u, v 를 어떻게 나눌지를 고민해야한다.

2. 괄호 문자열을 확인하는 방법은 stack 을 사용한다. 올바른 문자열은 () 일 때 pop() 을 하는 경우, 비어있는 스택이 되어야 한다.

3. u, v 를 나누는 방법은 여는 괄호 ( 와 닫는 괄호 ) 의 갯수가 동일할 때의 인덱스를 중심으로 나누면 된다. 예를 들어 ))((() 인 경우 ))(( , () 로 나눌 수 있다. ))(( 이 닫는 괄호 2개, 여는 괄호 2개로 일치하기 때문이다.

4. 나머지는 문제가 제공하는 순서대로 재귀를 만들어주면 된다.

배운점

• c++ 에서 배열을 반환하는 방법을 모르겠다. 백터나 pair 등은 확실히 반환되는 듯 한데 🤔

#include <string>
#include <stack>

using namespace std;

bool check_right(string str) {
    stack<char> s;
    for (int i = 0; i < str.size(); i++) {
        if (s.size() > 0 && s.top() == '(' && str[i] == ')') s.pop();
        else s.push(str[i]);
    }
    return s.empty() ? true : false;
}

string solve(string str) {
    if (str == "") return "";

    int cnt_open = str[0] == '(' ? 1 : 0;
    int cnt_close = str[0] == ')' ? 1 : 0;
    string u = "";
    string v = "";
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == '(') cnt_open++;
        else cnt_close++;
        if (cnt_open == cnt_close) {
            u = str.substr(0, i + 1);
            v = str.substr(i + 1, str.size());
            break;
        }
    }

    if (check_right(u)) return u + solve(v);
    string change_str = "";
    for (int i = 1; i < u.size() - 1; i++) {
        change_str += u[i] == '(' ? ')' : '(';
    }
    return '(' + solve(v) + ')' + change_str;
}

string solution(string p) {
    if(check_right(p)) return p;
    return solve(p);
}