[프로그래머스](Java) - 괄호 변환
문제 링크
문제 풀이
문제를 차근차근 읽으면서 진행했다.
v에 대해서는 재귀형식으로 돌아야하므로 dfs를 이용해서 접근해야 한다고 생각했다.
문자열을 우선 u,v로 쪼갠다.
임의의 변수 cnt를 (가 들어오면 --, )가 들어오면 ++ 시켜서 다시 0이 되는 순간이 균형잡힌 괄호 문자열이 되므로 그순간 break 시켜서 그동안의 문자열이 u, 남은 문자열이 v가 된다.public static String [] seperate(String p){ String [] result = {"",""}; //String[0] = u, String[1] =v; int cnt =0; for(int i=0; i<p.length(); i++){ if(p.substring(i,i+1).equals("(")){ cnt ++; }else{ cnt --; } result[0] +=p.substring(i,i+1); if(cnt==0){ result[1] = i==p.length()-1 ? "" : p.substring(i+1,p.length()); break; } } return result; }
얻은 문자열 u에 대해서 올바른 문자열인지 체크한다.
올바른 문자열이되기위해서는 ( 부터 시작이 되어야 하며, )가 (보다 더 먼저 등장하면 안된다.
그래서 ( 가등장할때는 ++, )가 등장할때는 -- 를 해주어 0보다 작아지게 되면 (가 더 먼저 등장했다는 뜻이므로 올바르지 않은 문자열이 된다.public static boolean chk(String p){ boolean res = true; int cnt =0; for(int i=0; i<p.length(); i++){ if(p.substring(i,i+1).equals("(")){ cnt ++; }else{ cnt --; } if(cnt<0){ res = false; } } return res; }
u가 올바른 문자열인경우 결과에 u는 더하고 v에 대해서는 다시 재귀를 돈다.
if(chk(result[0])){ //u가 올바른 문자열 answer += result[0]; answer+=dfs(result[1]); }
올바른 문자열이 아닌경우에는
else{ //올바른 문자열이 아닌경우 //4-1 String temp = "("; //4-2 temp+=dfs(result[1]); //4-3 temp+=")"; //4-4 temp+=revers(result[0]); //4-5 answer+=temp; }
를 돌게 되며
단계에 따라서 진행한다.
4-4단계의 경우 ( -> ) 로, ) -> (로 바꿔준다.public static String revers(String p){ String res = ""; p = p.substring(1,p.length()-1); if(p.length()==0){ return ""; }else{ for(int i=0; i<p.length(); i++){ if(p.substring(i,i+1).equals("(")){ res+=")"; }else{ res+="("; } } } return res; }
dfs의 시작 문자가 ""인경우에는 바로 return 하도록 한다.
if(p.equals(answer)){ return answer; }
코드
import java.util.*;
class Solution {
public String solution(String p) {
String answer = "";
answer = dfs(p);
//System.out.println(Arrays.toString(result));
return answer;
}
public static String dfs(String p){
String answer ="";
if(p.equals(answer)){
return answer;
}
String [] result = seperate(p);
//System.out.println(Arrays.toString(result));
if(chk(result[0])){
//u가 올바른 문자열
answer += result[0];
//p = result[1];
answer+=dfs(result[1]);
}else{
//올바른 문자열이 아닌경우
//4-1
String temp = "(";
//4-2
temp+=dfs(result[1]);
//4-3
temp+=")";
//4-4
temp+=revers(result[0]);
//4-5
answer+=temp;
}
return answer;
}
public static String [] seperate(String p){
String [] result = {"",""}; //String[0] = u, String[1] =v;
int cnt =0;
for(int i=0; i<p.length(); i++){
if(p.substring(i,i+1).equals("(")){
cnt ++;
}else{
cnt --;
}
result[0] +=p.substring(i,i+1);
if(cnt==0){
result[1] = i==p.length()-1 ? "" : p.substring(i+1,p.length());
break;
}
}
return result;
}
public static boolean chk(String p){
boolean res = true;
int cnt =0;
for(int i=0; i<p.length(); i++){
if(p.substring(i,i+1).equals("(")){
cnt ++;
}else{
cnt --;
}
if(cnt<0){
res = false;
}
}
return res;
}
public static String revers(String p){
String res = "";
p = p.substring(1,p.length()-1);
if(p.length()==0){
return "";
}else{
for(int i=0; i<p.length(); i++){
if(p.substring(i,i+1).equals("(")){
res+=")";
}else{
res+="(";
}
}
}
return res;
}
}
Author And Source
이 문제에 관하여([프로그래머스](Java) - 괄호 변환), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@courage331/프로그래머스Java-괄호-변환저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)