문제 링크 : 괄호 변환
그냥 문제에서 주어진 과정들을 차근차근 구현하면되는 간단한 문제이다.
문자열을 나누면서 다시 처음부터 수행하기 때문에 재귀를 사용해야한다.
과정에 재귀적으로 수행한다라는 힌트도 주어서 재귀를 사용해야한다는 것을 쉽게 알 수 있다.
균형잡힌 문자열 u,v로 분리할 때 u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하기 때문에 w를 탐색하며 최초로 균형잡힌 괄호 문자열이 완성된 순간의 문자열이 더 이상 균형잡힌 괄호 문자열로 분리할 수 없는 문자열이 된다. 그리고 나머지 문자열을 v로 반환하면 된다.
#include <string>
#include <vector>
using namespace std;
bool check(string w) {
int index=0;
for(char c : w) {
if(c=='(') {
index++;
} else {
index--;
}
if(index<0) return false;
}
return true;
}
string reverse(string u) {
string temp = "";
for(char c : u) {
if(c=='(') temp += ')';
else temp += '(';
}
return temp;
}
string solve(string w) {
if(check(w)) return w; // 올바른 괄호 문자열이거나 빈문자열이면 return
else {
string u="", v="";
int index=0;
for(int i=1 ; i<=w.size() ; i++) {
if(w[i-1]=='(') index++;
else index--;
if(index==0) { // 최초로 균형 잡힌 문자열이 완성된 순간
u = w.substr(0, i);
v = w.substr(i);
break;
}
}
if(check(u)) {
return u+solve(v);
} else {
string temp = "("+solve(v)+")";
u = u.substr(1, u.size()-2);
u = reverse(u);
temp += u;
return temp;
}
}
}
string solution(string p) {
string answer = "";
answer += solve(p);
return answer;
}