[Algorithm] 프로그래머스 '2020 KAKAO BLIND RECRUITMENT' C++ : 괄호 변환

 

 

 

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

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

 

u, v를 나누는 split 함수와

"올바른 괄호 문자열"인지 확인하는 is_right 함수 구현까지는 빨리 했다.

 

근데 재귀함수 사용에서 막혔다.

 

특히, 가장 헷갈렸던 부분은 

u, v를 글로벌 변수로 둬서 계속 바뀌는게 유지되는 상황 안에서

 

재귀함수 호출 후의 바뀐 u, v를 재귀함수가 호출된 곳으로 다시 돌아왔을때도 그대로 사용하게 돼서 꼬였다.

 

재귀함수를 호출하기 전에 그때의 u, v를 사용할 곳에 사용하고 나서 재귀함수를 호출하니까 해결

 

 

 

Code

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

using namespace std;

string answer = "", u = "", v = "";
int start_idx_of_v;

// "균형잡힌 괄호 문자열" u 분리
int split(string s) {
    int l = 0, r = 0;
    
    start_idx_of_v = 1;
    for(int i=0; i<s.size(); i++) {
        if(s[i]=='(') l++;
        else r++;
        
        if(l == r) return start_idx_of_v;
        
        start_idx_of_v++;
    }
}

// 올바른 괄호 문자열인지 확인
bool is_right(string s) {
    stack<char> tmp;
    
    for(char c: s) {
        if(c=='(') {
            tmp.push('(');
        }
        else {
            // 꺼내려는데 비었으면 false
            if(tmp.empty()) return false;
            tmp.pop();
        }
    }
    return true;
}

// 재귀 알고리즘 (주의: u, v가 글로벌 변수라 make_v 호출 전에 u와 v 값을 어디든 반영해놔야함)
string make_v(string s) {
    
    if(v == "") return "";
    
    // u, v 분리
    start_idx_of_v = split(s);
    u = s.substr(0, start_idx_of_v);
    
    // u가 "올바른 괄호 문자열"이면
    if(is_right(u)) {
        v = s.substr(start_idx_of_v);
        string res = u;
        return res + make_v(v);
    }
    
    // 아니면
    else {
        v = s.substr(start_idx_of_v);
        
        string tmp_u = u.substr(1, u.size()-2);
        string tmp_u_new = "";
        
        if(tmp_u != "") {
            for(char c: tmp_u) {
                if(c == '(') tmp_u_new += ")";
                else tmp_u_new += "(";
            }
        }
        
        return "(" + make_v(v) + ")" + tmp_u_new;
    }
}

string solution(string p) {
    if(p == "") return "";
    if(is_right(p)) return p;
    
    v = p;
    
    answer = make_v(v);
    
    return answer;
}