[JAVA] 2020 KAKAO BLIND RECRUITMENT 【괄호 변환】

---

처음에 )()(() 인 경우 u= [ )( ] 와 v= [ )(() ] 로 나눈 뒤 "()" + "()" +"()" 가 되어서 "()()()" 인줄 알았지만,

 

과정이 좀 달랐다.

 

)( 에서 앞 뒤 문자열을 제거하면 "" 빈 문자열만 남는다.

 

따라서, '(' 를 붙이고 v= [ )(() ] 를 다시 1단계부터 진행한 문자열을 붙이고 ')' 를 붙인다.

 

v = [ )(() ] 를 다시 1단계를 시작하면 u = [ )( ] 와 v = [ () ] 로 나눌 수 있으므로 

 

u는 또 다시 빈 문자열이 되고 '(' 를 붙이고 v = [ () ] 를 다시 1단계부터 진행한 문자열을 붙이고 ')' 를 붙인다.

 

v를 대상으로 또 1단계를 진행하면, 완전 문자열이므로 () 가 반횐된다.

 

따라서 일련의 과정을 run() 이라고 한다면

 

run( [ )()(() ] ) = '(' + run( [ )(()] ) + ')' = '(' + '(' + run( [ () ] ) + ')' + ')' = '(' + '(' + '()' + ')' + ')' = '((()))' 가 된다.

 

위처럼 그냥 문제가 알려준 대로 잘 구현하면 된다.

 

---

package LV2.괄호변환;

class Solution {
    StringBuilder ans;

    public String solution(String p) {
        ans = new StringBuilder();
        run(p);
        return ans.toString();
    }

    void run(String str){
        if(isRight(str)){
            ans.append(str);
            return;
        }else{
            String[] result = separate(str);
            String u = result[0];
            String v = result[1];
            if(!isRight(u)){
                ans.append("(");
                run(v);
                ans.append(")"+convert(u));
            }else{
                run(u);
                run(v);
            }
        }
    }
    String convert(String str){
        if(str.length()==2){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<str.length()-1;i++){
            if(str.charAt(i)=='('){
                sb.append(')');
            }else{
                sb.append('(');
            }
        }

        return String.format("%s",sb.toString());

    }
    String[] separate(String str){
        char ch = str.charAt(0);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==ch){
                sb.append(ch);
            }else{
                sb.deleteCharAt(sb.length()-1);
                if(sb.length()==0){
                    return new String[]{str.substring(0,i+1),str.substring(i+1)};
                }
            }
        }
        return new String[]{str,""};
    }

    boolean isRight(String str){

        int i = str.length()/2;

        while(i-->0){
            str = str.replace("()","");
        }
        if(str.length()==0){
            return true;
        }else{
            return false;
        }

    }
}