[알고리즘C++]괄호변환

오늘의 문제

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

괄호변환

나의 풀이

#include <string>
#include <vector>

using namespace std;

string solution(string p) {
    string answer = "";
    int size = p.size();
    if(size == 0)
        return answer;
    else{
        int l=0;
        int r=0;
        bool right = true;
        for(int i=0;i<size;i++){
            if(p[i] == '(')l++;
            else r++;
            if(l<r) right = false;

            if(l == r){ // 균괄문
                string u = p.substr(0, i+1);
                string v = p.substr(i+1, size -i-1);
                if(right){ // 올괄문
                    return u + solution(v);
                }else{
                    string s = '('+ solution(v) +')';
                    string uu = u.substr(1, u.size()-2);
                    for(int j=0;j<uu.size();j++){
                        if(uu[j] == '(')
                            uu[j] = ')';
                        else
                            uu[j] = '(';
                    }
                    return s+uu;
                }   
            }
        }
    }
}

모범 정답

#include <bits/stdc++.h>
using namespace std;

bool check(const string &a) {
    int r = 0;
    for (char ch : a) {
        if (ch == '(') ++r;
        else --r;
        if (r < 0) return false;
    }
    return r == 0;
}
string solution(string p) {
    if (p == "") return "";
    if (check(p)) return p;

    int i, t = 0;
    for (i = 0; i < p.size(); ++i) {
        if (p[i] == '(') ++t;
        else --t;
        if (t == 0) break;
    }

    string u = p.substr(0, i + 1);
    string v = p.substr(i + 1);

    if (check(u)) return u + solution(v);

    for (char &ch : u) ch = ch == '(' ? ')' : '(';
    return string("(") + solution(v) + ")" + u.substr(1, u.size() - 2);
}

배울 점

• for(char ch : a)이거를 많이 쓴다. 나도 써야지