사용한 것
- top-down을 사용하여 괄호 집합을 올바른 괄호 집합으로 변환
풀이 방법
- 문제에서 풀이 방법을 설명하고 있다. 따라서 구현만 해주면 된다.
- 하나의 괄호 집합은 '('의 수와 ')'의 수가 같아질 때 이다.
- 올바르지 않은 괄호 집합은 ')'가 '('보다 먼저 나오는 경우이다.
코드
class Solution {
public String solution(String p) {
return dp(p);
}
String dp(String p) {
if (p.equals("")) {
return p;
}
String u = "";
String v = "";
int num1 = 0;
int num2 = 0;
int idx = 0;
boolean illegal = false;
while (idx < p.length()) {
char c = p.charAt(idx);
if (c == '(') {
num1++;
} else {
if (num1 == 0) {
illegal = true;
}
num2++;
}
u += c;
idx++;
if (num1 != 0 && num1 == num2) {
break;
}
}
while (idx < p.length()) {
v += p.charAt(idx++);
}
if (illegal) {
String fixed = "(" + dp(v) + ")";
for (int i = 1; i < u.length() - 1; i++) {
char c = u.charAt(i);
if (c == '(') {
fixed += ")";
} else {
fixed += "(";
}
}
return fixed;
} else {
return u + dp(v);
}
}
}