[java] 프로그래머스 - 괄호변환
업데이트:
문제
프로그래머스-괄호변환
괄호 문자열을 입력받아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 코드를 작성하는 문제.
균형잡힌 괄호 문자열을 입력받아 올바른 괄호 문자열로 변환하기
- 설명
- 균형잡힌 괄호 문자열
‘(‘와 ‘)’의 갯수가 같은 경우 - 올바른 괄호 문자열
‘(‘과) ‘)’의 갯수가 같고, 짝도 모두 맞는 경우
균형잡힌 괄호 문자열 의 경우 다음과 같은 작성을 통해 올바른 괄호 문자열로 변환할 수 있다.
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. 생성된 문자열을 반환합니다.
- 균형잡힌 괄호 문자열
풀이
생성 함수 목록 및 설명
-
private boolean isCorrect(String p);
설명 : 올바른 괄호 문자열인지 판단하는 함수
매개변수 : 판단할 문자열
동작 내용 : p의 한 글자씩 반복하면서 ‘(‘는 1 증가, ‘)’는 1 감소
0보다 작아지거나, 반복 종료 후 0이 아닌경우 올바른 괄호 문자열이 아니다.
리턴 값 : 올바른 괄호 문자열인지 판단 결과 -
private String creation(String w);
설명 : 균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하는 함수
매개변수 : 균형잡힌 괄호 문자열
동작 내용 : 문제에서 주어진 균형잡힌 괄호문자열을 올바른 괄호 문자열로 변환하는 내용을 수행한다.
리턴 값 : 생성된 올바른 괄호 문자열 -
private String[] seperate(String w);
설명 : 균형잡힌 괄호 문자열을 u,v로 분리하는 함수
매개변수 : 균형잡힌 괄호 문자열 혹은 문자열
동작 내용 : 입력받은 문자열 w에서 균형잡힌 문자열까지의 idx를 찾는다.
idx를 기준으로 u, v로 분리해서 배열에 담는다.
리턴 값 : u, v가 담긴 string 배열
( u: 균형잡힌 괄호문자열로 더이상 분리할 수 없음, w에서 u를 제외한 문자열)
소스코드
class Solution {
public String solution(String p) {
return creation(p);
}
private boolean isCorrect(String p) {
// TODO Auto-generated method stub
int chk = 0;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '(') {
chk++;
} else {
chk--;
if (chk < 0) {
return false;
}
}
}
return chk == 0 ? true : false;
}
private String creation(String w) {
// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
if (w.trim().equals("")) {
return "";
}
if (isCorrect(w)) {
return w;
}
// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
String[] sep = seperate(w);
// 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
if (isCorrect(sep[0])) {
String result_v = creation(sep[1]);
// 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
return sep[0] + result_v;
}
// 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
else {
// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
StringBuilder sb = new StringBuilder();
sb.append("(");
// 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
sb.append(creation(sep[1]));
// 4-3. ')'를 다시 붙입니다.
sb.append(")");
// 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
for (int i = 1; i < sep[0].length() - 1; i++) {
if (sep[0].charAt(i) == '(') {
sb.append(")");
} else {
sb.append("(");
}
}
// 4-5. 생성된 문자열을 반환합니다.
return sb.toString();
}
}
private String[] seperate(String w) {
// TODO 균형잡힌 문자열로, 더이상 분리가 불가능함
String[] ans = new String[2];
// 1. 괄호의 갯수가 일치해야함
int left = -1;
int right = 0;
int idx = 0;
while (idx<w.length() && left != right) {
if (w.charAt(idx++) == '(') {
if(left==-1) {
left=0;
}
left++;
} else {
right++;
}
}
if(left==right) {
ans[0]=w.substring(0,idx);
ans[1]=w.substring(idx,w.length());
}else {
ans[1]=w;
}
return ans;
}
}
댓글남기기