[Programmers] 괄호 변환

import java.util.Stack;

class Solution {
   public String solution(String p) {
        String answer = solve(p);                
        return answer;
    }
    
    String solve(String str) {
    	if(str.equals("")) return "";
    	int divideIndex = divide(str);
    	String u = str.substring(0, divideIndex);
    	String v = str.substring(divideIndex);
    	    	
    	if(isOk(u)) return u + solve(v);
    	
    	String result = "(";
    	result = result + solve(v);
    	result = result + ")";
    	result = result + reverse(u);
    		
    	return result;
    }
    
    String reverse(String str) {
    	char[] charArr = str.toCharArray();
    	StringBuilder sb = new StringBuilder();
    	for(int i = 1; i < charArr.length - 1; i++) {
    		if(charArr[i] == '(') sb.append(")");
    		else if(charArr[i] == ')') sb.append("(");
    	}
    	return sb.toString();
    }
    
    int divide(String str) {
    	char[] charArr = str.toCharArray();
    	for(int i = 1; i <= charArr.length; i++) {
    		if(isBalenced(str.substring(0, i))) return i;
    	}
    	return -1;
    }
    
    boolean isBalenced(String str) {
    	char[] charArr = str.toCharArray();
    	int cnt1 = 0;
    	int cnt2 = 0;
    	for(int i = 0; i < charArr.length; i++) {
    		if(charArr[i] == '(') cnt1 ++;
    		else if(charArr[i] == ')') cnt2++;    		
    	}
    	return cnt1 == cnt2;    	
    }
    
    boolean isOk(String str) {
    	char[] charArr = str.toCharArray();
    	Stack<Character> stack = new Stack<>();
    	
    	for(int i = 0; i < charArr.length; i++) {
    		if(charArr[i] == '(') stack.push(charArr[i]);
    		else if(charArr[i] == ')') {
    			if(!stack.isEmpty()) stack.pop();
    			else return false;
    		}
    	}
    	
    	return stack.isEmpty();
    }
}