[프로그래머스](Java) - 괄호 변환

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60058

문제 풀이

문제를 차근차근 읽으면서 진행했다.
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;
    }
}