프로그래머스 문제 - 괄호 변환

프로그래머스 괄호 변환 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

'(' 와 ')' 로만 이루어진 문자열이 주어집니다.
'(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부르고 짝도 맞을 경우 올바른 괄호 문자열이라고 부릅니다.
균형잡힌 괄호 문자열을 아래와 같은 과정을 통해 올바른 괄호 문자열로 변경할 수 있습니다.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return해야 합니다.

문제 풀이

괄호 문자열을 탐색하고 변환하는데 재귀를 사용하라고 적혀있기 때문에 과정 순서대로 재귀를 작성하면 손쉽게 풀 수 있는 문제입니다.
문제를 이해하려고 하면 더 혼동될 수 있으니 주의해야합니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

bool checkCorrectString(string str)
{
    int bracketCnt = 0;
    
    for(int i = 0; i < str.length(); i++) //올바른 괄호 문자열인지 확인
    {
        if(str[i] == '(')
        {
            bracketCnt++;
        }else
        {
            bracketCnt--;
        }
        if(bracketCnt < 0)
        {
            return true;
        }
    }
    return false;
}

string checkString(string w)
{
    //빈 문자열이면 빈 문자열 반환
    if(w == "")
        return "";
    
    string u = "";
    string v = "";
    pair<int, int> brackets;
    
    brackets = make_pair(0, 0);

    //균형잡힌 괄호 문자열 탐색
    for(int i = 0; i < w.length(); i++)
    {
        if(w[i] == '(')
        {
            brackets.first++;
        }else
        {
            brackets.second++;
        }
        u = u + w[i];
        
        if(brackets.first != 0 && brackets.second != 0 && brackets.first == brackets.second)
        {
            v = w.substr(i+1);
            break;
        }
    }
    
    if(checkCorrectString(u))
    {
        string str = "(" + checkString(v) + ")";
        //첫번째와 마지막 문자를 제거한 문자열 생성
        string s = u.substr(1, u.length()-2);
        //이후 (와 )를 바꿔줌
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] == '(')
                s[i] = ')';
            else
                s[i] = '(';
        }
        str = str + s;
        return str;
        
    }else{
        return u + checkString(v);
    }
}

string solution(string p) {
    string answer = "";
    string str = "";
    
    answer = checkString(p);
    
    return answer;
}

출저

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