안녕하세요. 오늘은 프로그래머스의 괄호 변환문제를 풀어보겠습니다. 이 문제는 2020 KAKAO BLIND RECRUITMENT에서 출제되었습니다.
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60058
문제 풀이
균형잡힌 괄호 문자열인 w를 올바른 괄호 문자열로 변환하는 과정이 제일 중요하다고 생각한다.
✔ 1번 과정
입력이 빈 문자열일 때, 빈 문자열을 반환해야 한다. 해당 과정은 solution함수의 제일 첫 번째 줄에 썼다.
✔ 2번 과정 : cutParenthesis 함수 구현
- 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
2번 과정을 위해 cutParenthesis함수를 구현했다. u가 균형잡힌 문자열로 더 이상 분리할 수 없어야 하므로, uv배열을 만들어(uv[0]이 u, uv[1]이 v이다) '('와 ')'의 개수를 세서 개수가 같으면 uv[0]에 넣어버렸다. 그리고 나머지 괄호들은 uv[1]에 넣었다.
✔ 3번, 4번 과정 : makeBalancedString 함수 구현
- 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
- 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
해당 과정을 makeBalancedString함수에 그대로 구현했다. 이 함수에서는 whileLoop을 제때 끝내는 것이 중요한데, 1) 4번에서 4-5까지의 과정이 모두 수행되는 경우 2) v문자열이 없는 경우(함수에서 uv[1]이 ""인 경우) whileLoop변수를 false로 만들어 while문을 종료시켰다.
✔ 올바른 괄호 문자열인지 판단 : isBalancedString 함수 구현
Stack을 이용해서 올바른 괄호 문자열 여부를 판단했다. 괄호 짝이 맞으면 stack의 peek값을 뺀다.(poll) for문을 전부 돌았을 때, stack에 괄호가 하나라도 남아있으면 올바른 괄호 문자열이 아니며, stack에 괄호가 하나도 남아있지 않으면 올바른 괄호 문자열이다.
전체 코드
import java.util.*;
class Solution {
public String solution(String p) {
if(p.length() == 0) return "";
String answer = makeBalancedString(p);
return answer;
}
private String makeBalancedString(String p) {
boolean whileLoop = true;
String pCheck = p;
String[] uv = new String[2];
StringBuilder makeBalance = new StringBuilder();
while(whileLoop) {
uv = cutParenthesis(pCheck);
boolean uBalanced = isBalancedString(uv[0]);
if(uBalanced == true) {
makeBalance.append(uv[0]);
} else {
StringBuilder sb = new StringBuilder();
sb.append("(");
sb.append(makeBalancedString(uv[1]));
sb.append(")");
StringBuilder u = new StringBuilder();
u.append(uv[0]);
u.deleteCharAt(0);
u.deleteCharAt(u.length() -1);
if(u.length() != 0) {
for(String str : u.toString().split("")) {
if(str.equals(")"))
sb.append("(");
else
sb.append(")");
}
}
makeBalance.append(sb);
whileLoop = false;
}
pCheck = uv[1];
if(uv[1].equals("")) whileLoop = false;
}
return makeBalance.toString();
}
private String[] cutParenthesis(String p) {
String[] uv = {"",""};
StringBuilder sb = new StringBuilder();
int leftNum = 0;
int rightNum = 0;
for(int i=0; i<p.length(); i++) {
char c = p.charAt(i);
sb.append(c);
if(uv[0].equals("")) { //u를 만드는 과정
if(c == '(') leftNum++;
else if(c == ')') rightNum++;
if(leftNum == rightNum && leftNum != 0) {
uv[0] = sb.toString();
sb.delete(0, sb.length());
}
} else { //v를 만드는 과정
continue;
}
}
uv[1] = sb.toString();
return uv;
}
private boolean isBalancedString(String p) {
Stack<String> stack = new Stack<>();
if(p.length() == 0) return true;
for(String str : p.split("")) {
if(stack.size() != 0) {
String peek = stack.peek();
if(peek.equals("(") && str.equals(")"))
stack.pop();
else
stack.add(str);
} else {
stack.add(str);
}
}
if(stack.size() != 0) return false;
else return true;
}
}느낀점
✔ 전체적인 느낀점
추가 테스트 케이스를 찾을 필요 없이 한 번에 정답을 맞춰서 좋았다. 문제에서 주어진 사항들 중 4번(문자열 u가 "올바른 괄호 문자열"이 아니라면 수행해야 하는 과정)을 구현하는 것이 제일 어려웠다. makeBalancedString 함수를 만들고, u가 올바른 괄호 문자열이 아니라면 재귀함수를 돌도록 해서 해당 과정을 구현했다.
✔ 코드의 한계
많이 안 쓸수록 좋은 건 아니지만, StringBuilder를 너무 많이 선언했다. 내가 코드에서 선언한 StringBuilder들이 모두 쓸모있는 것 이었는지는 추후 찬찬히 살펴봐야겠다.
