+1 2020 KAKAO BLIND RECRUITMENT 괄호 변환

import java.util.*;

class Solution {
    public String solution(String p) {
        String answer  = dfs(p);
        return answer;
    }
    public static String dfs(String data){
        if(data.length() == 0) return ""; // 1. 빈 문자열 입력시 빈 문자열 반환
        String u="",v="";
        StringBuilder sb = new StringBuilder();
        int lcnt=0,rcnt=0;
        
        for(int i=0; i<data.length(); i++){
            if(data.charAt(i) == '(') lcnt++;
            else rcnt++;
            sb.append(data.charAt(i));
            
            if(lcnt == rcnt){
                v = data.substring(i+1);
                u = sb.toString();
                break;
            }
        }
        
        if(isCorrectString(u)){
            return u+dfs(v); // 만일 맞다면 v에 대하여 재귀적으로 수행한 값을 반환
        }else{
            sb = new StringBuilder();
            sb.append("(");
            sb.append(dfs(v));
            sb.append(")");
            
            u = u.substring(1,u.length()-1);
            for(int i=0; i<u.length(); i++){
                if(u.charAt(i) == ')')sb.append('(');
                else sb.append(')');
            }
            return sb.toString();
        }
    }
    
    public static boolean isCorrectString(String data){
        Stack<Character> st = new Stack<>();
        
        for(int i=0; i<data.length(); i++){
            if(data.charAt(i) == '(') st.push('(');
            else{
                if(st.isEmpty()) return false;
                else st.pop();
            }
        }
        return true;
    }
}

두번째

import java.util.Stack;
import java.util.stream.*;
import java.util.Arrays;

class Solution {
    Stack<Character> st = new Stack<>();
    
    public String solution(String p) {
        String answer = recur(p);
        return answer;
    }
    public String recur(String p){
        if (p.length()==0) return "";
        
        String u = "", v="";
        
        int lcnt=0,rcnt=0;
        
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i) == '(') lcnt++;
            else rcnt++;
            
            if(lcnt == rcnt){
                u = p.substring(0,i+1);
                v = p.substring(i+1);
                break;
            }
        }
        if(isGood(u)){
            // u가 올바른 문자열인 경우 v에 대하여 재귀 수행하고 나온 문자열 합쳐 반환
            return u+recur(v);
        }else{
            // 아니면 지시 사항대로 구현
            StringBuilder sb = new StringBuilder();
            sb.append('(');
            sb.append(recur(v));
            sb.append(')');
            
            u = u.substring(1,u.length()-1);
            for(int i=0; i<u.length(); i++){
                char el = u.charAt(i);
                if(el=='(') sb.append(')');
                else sb.append('(');
            }

            return sb.toString();
    }
    }
    /**
    이미 두 괄호의 갯수가 같음은 알고 있기 때문에
    제대로 닫혀있는지만 검사하자
    */
    public boolean isGood(String data){
        // 스택 이용하여 괄호 짝 맞추기
        st.clear();
        for(int i=0; i<data.length();i++){
            char cur = data.charAt(i);
            if(cur == '(') st.push(cur);
            else{
                if(st.isEmpty()) return false;
                st.pop();
            }
        }
        return true;
    }
}