![[프로그래머스,Level 2] 괄호 변환 (JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Frp3SX%2FbtqVcri2lKm%2F6NfTB1rawUeRaQfdIDP9xK%2Fimg.png)
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형 잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형 잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
- 첫 풀이 및 정답풀이
이 문제는 문제 자체가 이해하기 어렵게 써놓은 감이 없지 않아 있다. 이 문제를 풀기 위해서 우선적으로 이해하는 내용을 살펴보자. 문제 설명 부분은 읽지 않아도 큰 어려움이 없다. (읽어도 이해가 안되는 수준은 아니다.) 첫 번째 중요한 부분은 용어와 정의이다. 여기서 설명하는 중요한 개념이 두 가지가 있다.
첫 번째는 균형잡인 괄호 문자열이다. 이것이 의미하는 것은 단순히 한 문자열에 " ( "의 개수 == " ) "의 개수인 경우를 말한다. 대표적인 예로는 " ) (", " ( ( ) ) " 등이 있다.
두 번째는 올바른 괄호 문자열이다. 이것이 의미하는 것은 균형 잡힌 괄호 문자열 상태에서 괄호의 짝이 맞는 경우를 의미한다. 즉, 우리가 일반적으로 생각하는 괄호 쌍 ( )을 만족하는 상태를 말한다. 따라서 " ) ( "는 균형잡인 괄호 문자열이지만, 우리가 아는 괄호의 짝이 맞지 않기 때문에 올바른 괄호 문자열은 아니다. 올바른 괄호 문자열의 대표적인 예로는 " ( ) ", " ( ( ) ) " 등으로 열린 괄호가 나온 뒤, 닫힌 괄호가 나오는 경우가 있다.
문제에서 주어지는 문자열은 균형 잡힌 괄호 문자열이며, 이를 올바른 괄호 문자열로 변환하는 것이 핵심인 문제이다. 그리고 이 변환 방법은 문제에서 주어진다. 위에도 있는 이것이 그 과정이다. 하나씩 살펴보자.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
=> 빈 문자열은 빈 문자열을 반환한다.
2. 문자열 w를 두 "균형잡힌"균형 잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형 잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
=> 애매하다. 문자열 w는 입력 문자열을 의미하며, 이를 별개의 u와 v 균형잡힌 괄호 문자열로 분리해야 한다. 단, u는 더 이상 분리할 수 없어야 하기 때문에, 가장 작은 단위로 분리한다. 즉, ( 와 )의 개수가 처음 같아지는 순간을 의미한다. 그러면 자연스럽게 나머지 문자열은 v가 된다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
=> 위에서 분리한 u가 올바른 괄호 문자열, ( 와 )의 개수가 같고 쌍이 맞다면, v에 대해서 위의 과정을 다시 수행한다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
=> 3.에서 v에 대해 수행한 결과를 u에 붙인 후 반환한다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
=> 3. 과 다르게 올바른 괄호 문자열이 아니라면,
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
=> 새로운 문자열에 (를 붙인다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
=> v에 대해 1번 과정부터 다시 반복한 결과를 붙인다.
4-3. ')'를 다시 붙입니다.
=> )를 붙인다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
=> u의 첫 번째 마지막 문자를 제거하고 나머지는 괄호 방향을 뒤집어서 붙인다.
4-5. 생성된 문자열을 반환합니다.
=> 생성된 문자열을 반환한다.
여기까지가 모든 로직에 대한 내용이다. 필자는 이에 대한 구현 내용을 바탕으로 문제에서도 나와 있듯이 재귀를 이용해 풀어야 할 것 같다는 생각이 들었다. 단, 반환하는 값에 대한 내용이 애매하여 시간이 좀 걸렸다. 반환 값은 올바른 괄호 문자열로 변환하는 과정에 나와있듯이, u와 새롭게 만드는 문자열을 반환하면 된다.
구현을 시작할 때, 가장 먼저 고려한 것은 입출력 예제 1과 같은 경우이다. 문제에서 설명되어 있듯이 이미 올바른 괄호 문자열인 경우는 바로 반환하면 되는 부분이다. 이 처리는 이 경우를 포함해 변환과정에서도 필요하기 때문에 별도의 메서드 르 작성한다.
// 올바른 괄호 문자열 판단 메소드.
public static boolean check(String str){
// 1. ( 의 개수를 세는 변수.
int open = 0;
// 2. 첫 문자가 )인 경우는 올바른 괄호 문자열인 경우가 아니므로 false.
if(str.charAt(0) ==')') return false;
// 3. 문자열 탐색.
for(int i =0;i<str.length();i++){
// 4. (의 개수를 카운팅.
if(str.charAt(i) == '(') open++;
else {
// 5. )를 만나면 open 감소.
open--;
// 6. 카운팅 과정에서 open이 음수가 되면 (의 개수보다 )의 개수가 많아지는 순간이므로 올바른 괄호 문자열이 아니다. 따라서 false.
if(open<0) return false;
}
}
// 7. 위 조건을 모두 통과하면 올바른 괄호 문자열이다.
return true;
}이를 solution 메소드에서 호출하여 최초로 판단한다. 여기서 split 메서드는 균형 잡힌 괄호 문자열 -> 올바른 괄호 문자열 변환을 수행하는 메서드이다.
public String solution(String p) {
String answer;
// 1. 올바른 괄호 문자열이라면, 바로 문자열을 반환한다.
if(check(p))
return p;
// 2. 나머지 균현잡힌 괄호 문자열 => 올바른 괄호 문자열 변환 메소드 호출 및 answer에 저장.
answer = split(p);
return answer;
}이제 solution에서 호출된 split메서드를 살펴보자. 입력 문자열을 분리하여 저장하는 u와 v는 문자열에 대한 수정이 잦을 거라 생각되어 String 클래스보다 StringBuilder 클래스를 사용했다. 여기서의 reverse() 메서드는 변환 과정에서 u를 조작하는 메서드이다.
// 균형잡힌 괄호 문자열 -> 올바른 괄호 문자열 변환 메소드.
public static String split(String w){
// 1. 입력된 문자열 w를 u와 v로 나누어 저장하는 StringBuilder클래스 객체.
StringBuilder u = new StringBuilder();
StringBuilder v = new StringBuilder();
// 2. 빈 문자열인 경우, 빈 문자열을 반환.
if(w.length() == 0) return "";
// 3. (의 개수를 저장하는 변수.
int open = 0;
for(int i =0;i<w.length();i++){
// 4. 한 문자가 (인 경우 open은 증가.
if(w.charAt(i) == '(') open++;
// 5. )인 경우 open은 감소.
else open--;
// 6. 처음 open이 0이 된 경우가 가장 작은 단위의 "균형잡힌 괄호 문자열".
if(open == 0){
// 7. 해당 인덱스를 기점으로 u와 v로 분리.
u.append(w.substring(0,i+1));
v.append(w.substring(i+1,w.length()));
// 8. u가 "올바른 괄호 문자열"이라면,
if(check(u.toString())){
// 9. v에 대해 재귀호출 후, u에 이어 붙인다. 이 과정 후 break에 걸려 u를 반환하므로 변환 과정에 성립.
u.append(split(v.toString()));
// 10. u가 "올바른 괄호 문자열"이 아니라면,
}else{
// 11. 새로운 StringBuilder 객체 생성.
StringBuilder str = new StringBuilder();
// 12. (를 붙인다.
str.append("(");
// 13. v에 대해 재귀호출 후 붙인다.
str.append(split(v.toString()));
// 14. )를 붙인다.
str.append(")");
// 15. u를 조작해 붙인다.
str.append(reverse(u.toString()));
// 16. 새로운 문자열을 반환한다.
return str.toString();
}
break;
}
}
// 17. u가 올바른 문자인 경우에만 반환되는 u.
return u.toString();
}마지막으로 u를 변환 과정에 맞게 변경하는 reverse() 메서드이다.
// 변환 과정에 맞게 u를 변환하는 메소드.
public static String reverse(String str){
// 1. 변환한 문자열을 저장 할 StringBuilder 객체.
StringBuilder s = new StringBuilder();
// 2. 첫 번째, 마지막 문자를 제외하고 반복.
for(int i = 1; i<str.length()-1;i++){
// 3. ( -> )
if(str.charAt(i) == '(') s.append(")");
// 4. ) -> (
else s.append("(");
}
// 5. 새로운 문자열을 반환.
return s.toString();
}아래는 전체 코드이다.
class Solution {
// 변환 과정에 맞게 u를 변환하는 메소드.
public static String reverse(String str){
// 1. 변환한 문자열을 저장 할 StringBuilder 객체.
StringBuilder s = new StringBuilder();
// 2. 첫 번째, 마지막 문자를 제외하고 반복.
for(int i = 1; i<str.length()-1;i++){
// 3. ( -> )
if(str.charAt(i) == '(') s.append(")");
// 4. ) -> (
else s.append("(");
}
// 5. 새로운 문자열을 반환.
return s.toString();
}
// 올바른 괄호 문자열 판단 메소드.
public static boolean check(String str){
// 1. ( 의 개수를 세는 변수.
int open = 0;
// 2. 첫 문자가 )인 경우는 올바른 괄호 문자열인 경우가 아니므로 false.
if(str.charAt(0) ==')') return false;
// 3. 문자열 탐색.
for(int i =0;i<str.length();i++){
// 4. (의 개수를 카운팅.
if(str.charAt(i) == '(') open++;
else {
// 5. )를 만나면 open 감소.
open--;
// 6. 카운팅 과정에서 open이 음수가 되면 (의 개수보다 )의 개수가 많아지는 순간이므로 올바른 괄호 문자열이 아니다. 따라서 false.
if(open<0) return false;
}
}
// 7. 위 조건을 모두 통과하면 올바른 괄호 문자열이다.
return true;
}
// 균형잡힌 괄호 문자열 -> 올바른 괄호 문자열 변환 메소드.
public static String split(String w){
// 1. 입력된 문자열 w를 u와 v로 나누어 저장하는 StringBuilder클래스 객체.
StringBuilder u = new StringBuilder();
StringBuilder v = new StringBuilder();
// 2. 빈 문자열인 경우, 빈 문자열을 반환.
if(w.length() == 0) return "";
// 3. (의 개수를 저장하는 변수.
int open = 0;
for(int i =0;i<w.length();i++){
// 4. 한 문자가 (인 경우 open은 증가.
if(w.charAt(i) == '(') open++;
// 5. )인 경우 open은 감소.
else open--;
// 6. 처음 open이 0이 된 경우가 가장 작은 단위의 "균형잡힌 괄호 문자열".
if(open == 0){
// 7. 해당 인덱스를 기점으로 u와 v로 분리.
u.append(w.substring(0,i+1));
v.append(w.substring(i+1,w.length()));
// 8. u가 "올바른 괄호 문자열"이라면,
if(check(u.toString())){
// 9. v에 대해 재귀호출 후, u에 이어 붙인다. 이 과정 후 break에 걸려 u를 반환하므로 변환 과정에 성립.
u.append(split(v.toString()));
// 10. u가 "올바른 괄호 문자열"이 아니라면,
}else{
// 11. 새로운 StringBuilder 객체 생성.
StringBuilder str = new StringBuilder();
// 12. (를 붙인다.
str.append("(");
// 13. v에 대해 재귀호출 후 붙인다.
str.append(split(v.toString()));
// 14. )를 붙인다.
str.append(")");
// 15. u를 조작해 붙인다.
str.append(reverse(u.toString()));
// 16. 새로운 문자열을 반환한다.
return str.toString();
}
break;
}
}
// 17. u가 올바른 문자인 경우에만 반환되는 u.
return u.toString();
}
public String solution(String p) {
String answer;
// 1. 올바른 괄호 문자열이라면, 바로 문자열을 반환한다.
if(check(p))
return p;
// 2. 나머지 균현잡힌 괄호 문자열 => 올바른 괄호 문자열 변환 메소드 호출 및 answer에 저장.
answer = split(p);
return answer;
}
}구현 난이도는 어렵지 않지만, 문제에 대한 이해가 부족하여 시간이 걸린 케이스이다. 문제 자체는 문제에서 제시하는 변환 과정을 그대로 옮겨 담을 수 있으면 쉽게 해결할 수 있는 문제이다.