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

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

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

#include <string>
#include <vector>
#include <stack>
using namespace std;

bool isCorrect(string p){
    stack<char> s;
    for (char c: p){
        if (c=='(')
            s.push(c);
        else{
            if (s.empty())
                return false;
            else
                s.pop();
        }
    }
    return true;
}

string convert(string p){
    if (p.size()==0)
        return "";
    int pos=0;
    int cnt=0;
    string u="";
    string v="";
    while (pos<p.size()){      
        if (p[pos]=='(')
            cnt++;
        else
            cnt--;
        u+=p[pos];
        pos++;
        if (cnt==0)
            break;
    }
    if (pos<p.size())
        v+=p.substr(pos,p.size()-pos);  
    if (isCorrect(u))
        return u+convert(v);
    else{
        string temp="(";
        temp+=convert(v);
        temp.push_back(')');
        for (int i=1; i<u.size()-1; i++){
            if (u[i]=='(')
                temp.push_back(')');
            else
                temp.push_back('(');
        }
        return temp;
    }
}


string solution(string p) {
    if (isCorrect(p)){
        return p;
    } 
    string answer = convert(p);
    return answer;
}

 

명세대로 그대로 구현하기만 하면 되는 문제.

여기서 구현해야 될 부분은 균형잡힌 문자열로 쪼개는 부분, 올바른 균형잡힌 문자열인지 판정하는 부분이다.

 

균형잡힌 문자열로 쪼갤때는 (와 )가 나올 때 카운트를 증가, 감소시켜 주면서 카운트가 0이 될때 문자열을 쪼개준다.

올바른 균형잡힌 문자열인지 판단하는건 스택을 이용했다. ( 일때는 스택에 넣고, ) 일 때는 스택에 빼준다. ) 가 스택이 비었는데 나왔을 경우, 올바르지 않다고 판단한 후 false를 리턴한다.