제출 코드
- 사용 알고리즘 :
스택,재귀
괄호 짝을 비교하는 문제였기에, 자료구조로 스택을 사용하여 풀이했다. 문제에 로직을 상세하게 적어줘서 그대로 짜면 되는 문제였다. 올바른 괄호 문자열로 변환하는 메서드 하나 만들어두고, 내부에서 조건에 따라 재귀를 시행하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;
class Solution {
static String change(String s){ 입력받은 문자열을 올바른 괄호 문자열로 변환
int len = s.length();
if(len==0) return "";
int left=0, right=0;
String u="", v="";
for(int i=0; i<len; i++){
if(s.charAt(i)=='(') left++;
else right++;
if(left == right) {
u = s.substring(0, ++i);
v = s.substring(i, len);
break;
}
}
if(check(u)) return u + change(v);
else{
String tmp = "(" + change(v) + ")";
int tmp_len = u.length()-1;
for(int i=1; i<tmp_len; i++){
tmp += (u.charAt(i)=='(' ? ")" : "(");
}
return tmp;
}
}
static boolean check(String s){ // 입력받은 문자열이 올바른 괄호 문자열인지 체크
Stack<Character> stack = new Stack<Character>();
int len = s.length();
for(int i=0; i<len; i++){
char now = s.charAt(i);
if(stack.size()==0) stack.push(now);
else{
int pre = stack.peek();
if(pre=='(' && now==')') stack.pop();
else stack.push(now);
}
}
if(stack.size()>0) return false;
else return true;
}
public String solution(String p) {
return change(p+"");
}
}