[프로그래머스 2레벨] 괄호 변환 (C++)

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

bool check(string tmp)
{
    stack<char>st;
    for(auto i : tmp)
    {
        if(i == '(') st.push(i);
        else 
        {
            if(st.empty()) return false; //올바르지 않은 문자열
            st.pop();
        }
    }
    return st.empty();
}

string solution(string p) {
    string answer = "";
    string u = "", v = "";
    if(p.empty()) return p; // 조건 1
    
    int cnt1 = 0, cnt2 = 0;
    for(int i=0; i<p.size(); i++) //조건 2
    {
        if(p[i] == '(') cnt1++;
        else cnt2++;
        
        if(cnt1==cnt2)
        {
            u = p.substr(0, cnt1 + cnt2);
            v = p.substr(cnt1 + cnt2);
            break;
        }
    }
    
    if(check(u)) answer = u + solution(v); //조건 3~3-1
    else
    {
        answer += "("; //조건 4-1
        answer += solution(v); // 조건4-2
        answer += ")"; //조건 4-3
        
        for(int i=1; i<u.size()-1; i++) //조건 4-4~4-5
        {
            answer += (u[i] == ')' ? '(' : ')');
        }
    }
    
    return answer;
}

 

복잡해 보이지만 조건을 차근차근 해결해나가면 되는 문제이다.

먼저 조건 1 같은 경우는 간단하게 입력받은 문자열이 비었으면 바로 해당 문자열을 반환해준다.

 

2번을 보면 입력받은 문자열을 u, v로 분리해야 한다.

'(' 개수와 ')' 개수를 카운팅 하기위한 변수 2개를 선언하고, 각 변수의 개수가 똑같을 때를 기준으로 분리 시켜준다.

이때 u에 대해서 균형잡힌 괄호 문자열이 맞는 지 체크를 하게 된다.

이는 stack으로 간단히 체크가 가능한데, 만약 스택이 비었는데 ')'이 먼저 나온다면 균형이 어긋난 것이다.

이외에는 '('의 경우 push, ')' 경우 pop을 하며 최종 스택이 비었다면 짝이 전부 맞는 균형 잡힌 문자열인 것이다.

 

위 체크를 통해 3번 조건을 수행하는데, 조건에 따라 solution 함수로 재귀를 통해 처음 과정을 반복한다.

마찬가지로 체크를 통해 4번 조건을 수행하는데, 4-1~4-3은 주어진 그대로 수행해주면 된다.

4-4의 경우 첫 번째와 마지막 문자를 제거하기 위해 반복문의 인덱스를 조정해주고, 현재 문자를 기준으로 삼항연산자를 통해 반대로 뒤집어 주었다.