[DFS 조합] 프로그래머스 괄호 변환 C++

 

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

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

w를 u와 v의 조합으로 분리

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

using namespace std;

string dfs(string p, int a, string answer)
{
    stack<char> s;
    if (p.length() == a) return "";
    
    int l = 0;
    int r = 0;
    
    for(int i=a; i<p.length(); i++) {
        if (p[i]=='(') {
            l++;
            s.push(p[i]);
        }
        else if (p[i] == ')') {
            r++;
            if (s.size()!=0) // empty X {
                if (s.top()=='(') s.pop();
            }
        }
        
        // 균형잡힌 괄호 문자열
        if (l==r) {
        	// 올바른 괄호 문자열
            if(s.empty()) {
                answer=p.substr(a,i+1-a); // u
                answer+=dfs(p, i+1, answer); // v
                return answer;
            }
            // 올바른 괄호 문자열X
            else {
                string str = "(";
                str+=dfs(p, i+1, answer); // v
                str+=')';
                
                string temp = p.substr(a+1,i-(a+1)); // u
                
                // 나머지 괄호 방향 뒤집기(문자열 뒤집기X)
                for(int i=0; i<temp.length(); i++) {
                    if (temp[i]=='(') temp[i]=')';
                    else temp[i]='(';
                }
                
                str+=temp;
                return str;
            }
        }
    }
    return answer;
}

string solution(string p) { 
    string answer = "";
    answer = dfs(p, 0, answer);
    
    return answer;
}