[프로그래머스,Java] Level2:괄호 변환

 

문제분석

설명서대로만 하면된다. 이 문제는 설명서대로 정확하게 구현이 가능한지를 묻는다.

 

1. 빈 문자열이면 빈 문자 반환

->이거는 간단하다.

 

2. 문자열 w를  두개의 "균형잡힌 괄호" 분리.

-> u는 균형잡힌 괄호문자열이되면 바로 끝, v는 빈 문자열이 될수있음

 

how? ( 갯수와 )갯수를 각각 세서, 동일해지면 문자열을 분리해서 저장한다.

 

3.분리한 문자열 u가 올바른 문자열이면 v를 1단계부터 다시 재귀를돌린다.

-> 문자열 u뒤에 이어서 재귀를돌린v를붙힌다.

 

how? 올바른지판별은, Stack을 사용해서 판별하자.  Pop과 입력값이 같다면 짝이맞으므로 제거하다보면,

Stack의 문자열이 0이되는데, 이때가 올바른 괄호가된다.

 

4.분리한 문자열 u가 올바른 문자열이 아니라면,

-> 빈 문자열에 첫번째문자 '('를 붙이고,  재귀를돌린 v를 붙힌다.

->')'를 붙히고,  u의 첫번째 마지막문자를 제거하고 나머지문자열을 뒤집는다.

 

how? replace문을 사용하여, 괄호를 서로 뒤집는다.

 

 

재귀를 돌려라는 설명문이니, 재귀문을 작성하도록한다.

 

문제풀이

import java.util.*;
class Solution {
    static String result="";
    public String solution(String p) {
        recursive(p);
        return result;
    }
    
    public static String recursive (String w){
        String u="";
        String v="";
        
        // 1번 빈문자열 확인
        if(w==""){
            return w;
        }
        
        //2번 균형잡힌 문자열로 분리하기
        for(int i=2;i<=w.length();i+=2){
            u=w.substring(0,i);
            v=w.substring(i);
            int left =0;
            int right=0;          
            for(int j=0;j<u.length();j++){
                if(u.charAt(j)=='('){
                    left++;
                }
                else{
                    right++;
                }
            }        
            if(left==right){
                break;
            }
        } 
        boolean flag = true;
        //조건 3번: u 가 올바르면 이어붙이고 v를재귀
        Stack<String> confirm = new Stack<>();
        for(int i=0;i<u.length();i++){ 
        if(u.charAt(i)=='('){
            confirm.push("(");
        }
        else{
            if(confirm.empty()){
                flag=false;
                break;
            }
            else{
                confirm.pop();
            }
        }
    }   
        //3-1 올바른 괄호 문자열이면 v를 재귀 + u를 result 더하기
        if(flag==true){
            result+=u+recursive(v);
            
        }
        //조건4: 올바른 문자열이 아닌경우
        else{
            result+="("+recursive(v);
            u=u.substring(1,u.length()-1);
            u=u.replace("(","1");
            u=u.replace(")","2");
            u=u.replace("1",")");
            u=u.replace("2","(");
            result+=")"+u;
        }
                
        return result;
    }
}