🔗 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60058
🤔 문제
'(' 와 ')'로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열 이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))(" 와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 "(()))("
와 같은 문자열은 균형잡힌 괄호 문자열이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열이면서 동시에 올바른 괄호 문자열입니다.
📌 문제에서 제시한 방법
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. 생성된 문자열을 반환합니다.😮 문제 해결 방법
문제를 따라가다 보면 이해가 안되는 부분이 있었다.
문제에서 제시한 방법 2번을 읽어보면 **"균형잡힌 괄호 문자열" u,v로 분리합니다.** 라고 작성되어있다. 필자는 문제 풀이 당시 균형 잡힌 괄호 문자열이 나오는 가짓수는 여러가지가 있다고 생각해 시간을 많이 잡아먹었다.
간단하게 설명하자면, 문자를 하나씩 가져오면서 처음으로 균형잡힌 괄호 문자열이 되면 u,v로 분리해주면 되는 것이다.
")(()()"라는 문자열이 있다면, u = ")(" v="()()"가 되는 것이다.
여기서 u는 올바르지 않은 문자열, v는 올바른 문자열이다.
이제 문제를 예를 가지고 풀어보자.
"))((()" 라는 입력이 들어온다면, u = "))((" , v = "()"가 될 것이다. (2번 과정)
u가 올바른 문자열이 아니므로 4번 과정을 그대로 이어나간다.
"(" + function(v) + ")"가 될것이다. (4-1,2,3 과정)- 첫번째 function(v) → u =
"()", v = ""가 되고, u가 올바른 문자열이므로 u에 두번째 function(v)를 이어붙힌다. 여기서 두번째 function(v)에 빈칸이 들어가므로 빈칸을 return해주고 결국 첫번째 function(v)는"("+")"+"", 즉"()"을 return 한다. - 1번의 function(v)가 나왔으므로, "(())"값이 될것이다.(4-3까지의 과정)
- 현재 u값인
"))(("에서 첫번째 문자와 마지막 문자를 제거해주면u = ")("가 된다. 그리고 남은 문자열인")("를 방향을 바꿔주고 3번의 문자열 뒤에 붙혀준다. (4-5 까지의 과정) - 생성된 문자열
"(())()"을 return한다.
문제에서 제공하는 용어의 파악와 문제가 제시한 방법을 구현하면 많은 생각을 할 필요 없이 구현됨을 알 수 있다.
아래는 Java로 구현한 코드이다.
🚩 JAVA 코드
package com.algorithm.Programmers.Lv2;
import java.util.Stack;
// 프로그래머스 LV2(괄호 변환)
public class Solution_60058 {
public static void main(String[] args) {
System.out.println(solution("))((()"));
}
public static String solution(String p) {
// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
if(p.equals(""))
return "";
StringBuilder answer = new StringBuilder();
StringBuilder sb = new StringBuilder(p);
StringBuilder u = new StringBuilder();
StringBuilder v = new StringBuilder();
int open =0; // ( 인 경우
int close=0; // ) 인경우
// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
// 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
for(int i=0;i<sb.length();i++){
if(sb.charAt(i)=='(')
open++;
if(sb.charAt(i)==')')
close++;
//균형 괄호 문자열 경우
if(open==close){
u.append(sb.substring(0,i+1));
v.append(sb.substring(i+1));
break;
}
}
// 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
// 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
if(isCorrect(u.toString())){
return u.append(solution(v.toString())).toString();
}
// 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
// 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
// 4-3. ')'를 다시 붙입니다.
answer.append("(").append(solution(v.toString())).append(")");
u.deleteCharAt(0);
u.deleteCharAt(u.length()-1);
answer.append(swap(u.toString()));
return answer.toString();
}
//옳바른 문자열인지 확인
public static boolean isCorrect(String p){
Stack<String> st = new Stack<>();
for(String s:p.split("")){
// ( 만 스택에 넣어줌
if(s.equals("("))
st.push(s);
// 스택엔 ( 만 있으므로 )를 만나면 ( 를 빼줌
if(s.equals(")") && !st.isEmpty())
st.pop();
}
//스택 사이즈가 0이면 옳바른 문자열
//0이 아닌 경우 ( 가 남아있음
return st.size() < 1;
}
// 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
public static String swap(String u){
StringBuilder swapString = new StringBuilder();
for(char c : u.toCharArray()){
if(c=='(')
swapString.append(")");
if(c==')')
swapString.append("(");
}
return swapString.toString();
}
}
📄 정리
문제 해석에 애를 먹어 생각보다 많은 시간을 소비한 것 같다.
문제를 자세히 읽고 다양한 예시를 혼자 해보면서 하면 더 빠르게 해결할 수 있었을 것 같다.
문제에서 제시한 방법을 잘 읽고 적용하는 것도 하나의 실력이라 생각한다.
