[프로그래머스] 괄호 변환 -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. 생성된 문자열을 반환합니다.

문제 이해

• 문자열의 괄호는 "(", ")" 의 개수가 같은 "균형잡힌 괄호 문자열"이다. 알고리즘을 수행해 "올바른 괄호 문자열"로 변환하게 만들어야 한다.
• 문자열을 받았을때 빈문자열, "올바른 괄호 문자열" 로 받는다면 그대로 값을 리턴해준다.
• 문제 풀이를 보면 재귀적으로 수행하여 결과를 문자열을 이어 붙여라 ~ 라고 되어있다. DFS 방법으로 재귀식으로 풀었다.
• 문자열을  u = " 균형잡힌 괄호 문자열 " , v = " 균형잡힌 괄호 문자열 " 로 분리한다. 
• 문자열의 길이만큼 반복하면서 "(" 나오면 ++, ")" 나오면 -- 를 하면서 cnt값이 0이되는 값의 index로 u,v 로 나누었다.
• u가 "올바른 괄호 문자열" 라면 return u + dfs(v)
• u가 "올바른 괄호 문자열"이 아니라면 return "(" + dfs(v) + ") + u의 첫번째 마지막 문자열 제외한 모든괄호를 뒤집은 문자열
• 재귀를 돌면서 완성된 문자열이 "올바른 괄호 문자열"이 될때까지 실행한다.

class Solution {
    public String solution(String p) {
        String answer = "";
        if("".equals(p) || checkYn(p)) return p;
        
        return dfs(p);
    }
    
    public String dfs(String p){
        
        if(checkYn(p)) return p;
            
        int cnt = 0;
        String u = "";
        String v = "";
        for(int i = 0; i<p.length(); i++){
            String tmp = p.substring(i,i+1);
            
            if("(".equals(tmp)){
                cnt++;
            }else if(")".equals(tmp)){
                cnt--;
            }
            
            if(cnt == 0){
                u = p.substring(0,i+1);
                v = p.substring(i+1);
                break;
            }
        }
        
        if(checkYn(u)){
            return u + dfs(v);
        }else{
            String str = "";
            for(int i = 1; i<u.length()-1; i++){
                if("(".equals(u.substring(i,i+1))){
                    str += ")";
                }else{
                    str += "(";
                }
            }
            
            return "(" + dfs(v) + ")" + str;
        }
    }
    
    // 올바른 괄호 문자열 체크
    public boolean checkYn(String str){
        int cnt = 0;
        for(int i = 0; i<str.length(); i++){
            String tmp = str.substring(i,i+1);
            
            if("(".equals(tmp)){
                cnt++;
            }else if(")".equals(tmp)){
                cnt--;
            }
            
            if(cnt < 0) return false;
        }
        
        return true;
    }
}