👀 문제
https://programmers.co.kr/learn/courses/30/lessons/60058
👊 도전
1. 설계
- 문제에 주어진 알고리즘대로 진행한다.
- 이때 u는 문자열 w의 처음부터 확인하여 처음으로 올바른 문자열인 곳에서 자른다.
2. 구현
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
/**
*
* @author HEESOO
*
*/
import java.util.Stack;
class Solution {
public String solution(String p) {
if(p.length()==0) return "";
int idx=splitIdx(p);
String u=p.substring(0, idx);
String v=p.substring(idx, p.length());
if(isCorrect(u)) return u+solution(v);
String result="("+solution(v)+")";
u=u.substring(1, u.length()-1);
return result+reverse(u);
}
public static int splitIdx(String p) {
int open=0, close=0;
for(int i=0;i<p.length();i++) {
if(p.charAt(i)=='(') open++;
else close++;
if(open==close) return i+1;
}
return p.length();
}
public static boolean isCorrect(String p) {
Stack<Character> st=new Stack<>();
for(int i=0;i<p.length();i++) {
if(p.charAt(i)=='(') st.push('(');
else if(st.isEmpty()) return false;
else st.pop();
}
if(st.isEmpty()) return true;
else return false;
}
public static String reverse(String p) {
String result="";
for(int i=0;i<p.length();i++) {
if(p.charAt(i)=='(') result+=")";
else result+="(";
}
return result;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- splitIdx()로 u와 v를 나눈다
- splitIdx()는 문자열 w에서 u와 v를 나누는 인덱스를 리턴한다.
- ’(‘와 ‘)’가 같은 개수가 될 때 그 인덱스를 리턴하여 그 다음 인덱스를 리턴하여 u를 substring으로 자를 수 있게 한다.
- ’(‘와 ‘)’의 개수가 같지 않다면 균형잡힌 괄호가 아니므로 p.length()를 리턴하고, 더 이상 분리할 수 없으므로 u는 w가 된다.
- isCorrect()로 올바른 문자열인지 확인한다
- 스택을 이용하여 ‘(‘와 ‘)’가 올바른 문자열인지 확인한다.
- ’(‘인 경우 스택에 집어놓고 ‘)’일 때 하나씩 뺀다.
- ’)’인데 스택안에 값이 없을 경우 올바른 문자열이 아니므로 false를 리턴한다.
- for문을 빠져나온 후 스택이 비었다면 true를 리턴한다.
- isCorrect()에서 true를 리턴받았다면 올바른 문자열이므로 u에 v에 대한 알고리즘을 수행한 값을 붙여 리턴한다.
- 아닐 경우, 알고리즘 4번에 따라 진행한다.
- reverse()로 문자열 괄호 방향을 뒤집는다
- ’(‘이면 ‘)’로 바꾸고, ‘)’면 ‘(‘로 바꿔 문자열을 리턴한다.