0. 문제
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
1. 풀이
class Solution {
// 반복
static String replay(String u, int count, int repeat) {
String s = u.replace("()", "");
count++;
if(count==repeat) {
return s;
}
return replay(s, count, repeat);
}
// 올바른 문자열인지 체크
static boolean check(String u) {
int count = 0;
int repeat = u.length()/2;
String s = replay(u, count, repeat);
return s.equals("") ? true : false;
}
// 균형 문자열 나누기
static String[] balance(String q) {
String result[] = new String[2];
int left = 0;
int right = 0;
for(int i=0; i<q.length(); i++) {
if(q.charAt(i)=='(') {
left++;
}
else {
right++;
}
if(left==right) {
result[0] = q.substring(0, left+right);
result[1] = q.substring(left+right, q.length());
break;
}
}
return result;
}
// 괄호 방향 바꾸기
static String reverse(String u) {
StringBuilder result = new StringBuilder();
for(int i=0; i<u.length(); i++) {
if(u.charAt(i)=='(') {
result.append(')');
}
else if(u.charAt(i)==')') {
result.append('(');
}
}
return result.toString();
}
// 문자열 교정하는 메인 함수
static String correct(String p) {
String answer = "";
if(p==null) {
return p;
}
String u = balance(p)[0];
String v = balance(p)[1];
if(u==null) {
return "";
}
boolean isCorrect = check(u);
if(isCorrect) {
return u+correct(v);
}
else {
String result = "(" +correct(v)+ ")";
u = u.substring(1, u.length()-1);
return result+reverse(u);
}
}
public String solution(String p) {
return correct(p);
}
}2. 설명
이 함수는 재귀 문제이다. 따라서 메인 흐름을 잘 찾아내는 것이 가장 중요하다.
만약 흐름을 찾지 못하고 꼬여버리면 무한 루프에 빠지게 되므로, 꼭 주의하자!
하지만 이 문제는 이미 구현 과정이 제시되어 있으므로, 그대로 따라해주면 된다. 해당 풀이의 메인 흐름은 다음과 같다.
- null값 체크
- u, v 문자열 나누기
- v 문자열 null 체크
- u가 균형 문자열인지 체크
- if-else로 재귀 적용
- 괄호 방향 바꾸기
우선 2부터 찬찬히 알아보자.
u, v 문자열 나누기
// 균형 문자열 나누기
static String[] balance(String q) {
String result[] = new String[2];
int left = 0;
int right = 0;
for(int i=0; i<q.length(); i++) {
if(q.charAt(i)=='(') {
left++;
}
else {
right++;
}
if(left==right) {
result[0] = q.substring(0, left+right);
result[1] = q.substring(left+right, q.length());
break;
}
}
return result;
}이 과정은 간단하다.
u, v로 나눌 때 u는 최소 단위의 균형 문자열이어야 하므로, 정의에 따라 (와 )의 갯수가 같아지는 시점에서 substring으로 문자열을 잘랐다.
v 문자열 null 체크
해당 메서드는 재귀 메서드이다.
따라서 앞의 "문자열 쪼개기 과정"을 계속 거칠 것이고, 문자열은 점점 작아질 것이다.
그러다 더이상 쪼갤 수 없어서 null값을 반환한다면?
당연히 오류가 날 것이다!
문제에 따르면, v 문자열은 null값이 허용되지만, u 문자열은 그럴 수 없다.
따라서 올바른 문자열 확인 메서드에서 u문자열을 받고 null 오류를 내기 전에, 미리 체크를 해둔다.
// check 메서드가 확인하기 전에 null 처리
if(u==null) {
return "";
}
// u 문자열이 올바른 문자열인지 확인
boolean isCorrect = check(u);u가 균형 문자열인지 체크
이 부분에서 시간이 좀 걸렸지만, 의외로 해결책은 간단했다.
올바른 문자열은 짝이 맞는 문자열이다.
그렇다면 확인하는 방법은 짝을 제거해주면 된다.
// 반복
static String replay(String u, int count, int repeat) {
// 짝을 제거
String s = u.replace("()", "");
count++;
if(count==repeat) {
return s;
}
return replay(s, count, repeat);
}
// 올바른 문자열인지 체크
static boolean check(String u) {
int count = 0;
int repeat = u.length()/2;
String s = replay(u, count, repeat);
return s.equals("") ? true : false;
}짝이 맞는다는 건 "( )" 형태로 되어 있다는 것이다.
따라서 replace를 이용하여, "( )"를 모두 없애주었다.
// 짝을 제거
String s = u.replace("()", "");하지만 이를 계속 돌리게 되면, 무한루프에 빠진다.
따라서 최대 반복 횟수인 repeat를 "길이/2"로 지정해 주었다.
그 이유는 문자 2개씩 replace()하기 때문에, 모두 바꾼다고 하더라도 길이/2만큼만 replace()할 수 있다.
// 반복
static String replay(String u, int count, int repeat) {
// 짝을 제거
String s = u.replace("()", "");
count++;
// 최대 반복수에 도달하면 반환
if(count==repeat) {
return s;
}
return replay(s, count, repeat);
}
// 올바른 문자열인지 체크
static boolean check(String u) {
int count = 0;
// 최대 반복수 제공
int repeat = u.length()/2;
String s = replay(u, count, repeat);
return s.equals("") ? true : false;
}따라서 check()에서 최대 반복수를 주고 replay()에서 재귀를 돌린 후, count가 최대 반복수에 도달하면 재귀를 끝내도록 처리했다.
if-else로 재귀 적용
솔직히 이 부분은 문제에 "이 부분은 재귀를 적용하세요~"라고 대놓고 나와 있어서, 건너 뛰도록 하겠다.
(문제의 부분. 정말 딱 저렇게만 짜면 된다.)
// 올바른 문자열 이라면
if(isCorrect) {
return u+correct(v);
}
//아니라면
else {
String result = "(" +correct(v)+ ")";
u = u.substring(1, u.length()-1);
return result+reverse(u);
}괄호 방향 바꾸기
역시 생략한다. else-if문으로 방향을 바꿔주면 된다.
// 괄호 방향 바꾸기
static String reverse(String u) {
StringBuilder result = new StringBuilder();
for(int i=0; i<u.length(); i++) {
// (를 )로
if(u.charAt(i)=='(') {
result.append(')');
}
// )를 (로
else if(u.charAt(i)==')') {
result.append('(');
}
}3. 결론
재귀에 대해서는 그냥 "아 자체적으로 반복하는 함수구나"라는 것만 알았는데, 여러번 무한 루프도 빠지고 null 오류도 나고 하면서 많은 것을 알게 되었다.
어떨 때 사용해야 하는지, 무한 루프에 빠지지 않기 위해 뭘 먼저 생각해야 하는지 등 많은 부분을 깨달았다.
하지만 완벽히 내 것이 된건 아닌 느낌이다.
재귀와 관련하여 타 사이트에서 좀 더 풀어봐야 할 것 같다.
