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

🔮문제

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

🔮풀이

1. P가 빈 문자열인 경우, 빈 문자열 "" 반환

2. 올바른 문자열인 경우, 입력 문자열 반환

3. 균형잡힌 문자열인 경우

 3-1. u + v로 분리 (u : 균형, 분리x , v : 빈 문자열 ok)

 3-2. u가 올바른 문자열인 경우, u + v(1번부터 재귀) 반환

 3-3. u가 올바른 문자열이 아닌 경우, 문제의 4번 과정 수행 (recursive 함수 , u 문자열 첫째 마지막 문자 삭제후 뒤집기)

 

이 문제 풀이의 관건은 2가지 함수를 설정하는 것이다.

1) 올바른 문자열인지 확인하는 함수

2) u + v로 분할하는 recursive 함수

 

🔮코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

/*
개수만 같은 경우 -> 균형잡힌
개수 + 짝이 모두 맞을 경우 -> 올바른
올바른 문자열 결과 반환

-균형잡힌 문자열일 경우
1. 빈 문자 -> 빈 문자 반환
2. w = u + v 로 분리 (u: 균형, 분리X, v: 빈문자열 ok)
2-1. u가 올바른 문자열이면 v를 2번 과정 수행
2-2. u가 올바른 문자열 아니면 4번 과정 수행

*/
using namespace std;

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

string func(string p){
    //1. 빈 문자열인 경우 빈 문자열 반환
    if(p == "")
        return "";
    string u = ""; string v = "";
    int left = 0; int right = 0;
    //2. 균형잡힌 문자열이 되면 u, v 로 분리
    int size = p.size();
    for(int i=0; i< size; i++){
        if(p[i] == '('){
            left++;
        }
        else
            right++;
        if(left == right){
            u = p.substr(0, i+1);
            v = p.substr(i+1);
            break;
        }
    }
    //3. u가 올바른 문자열이면 v에 대해 1부터 재귀 수행
    if(isRight(u)){
        return u + func(v);
    }
    //4. u가 올바른 문자열이 아니면
    else{
        // 4-1 ~ 4-3
        string tmp = '(' + func(v) + ')'; 
        // 4-4
        u = u.substr(1, u.size()-2); 
        for(int i=0; i<u.size(); i++){
            if(u[i] == '('){
                tmp += ')';
            }
            else
                tmp += '(';
        }
        return tmp;
    }
}

string solution(string p) {
    if(p == "")
        return "";
    return func(p);
}