[알고리즘_풀이] 괄호변환 - 카카오 공채

https://programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

import java.util.Stack;
class Solution {
    public String solution(String p) {
        String answer = "";
                
        if(isRightString(p) == true) return p; // 올바른 문자열이면 바로 자기자신 리턴한다.
        
        // 여기서부터는 균형잡힌 문자열일 경우만 있다. 
        // 올바른 문자열로 바꾸는 함수가 결과 값을 리턴하고 이게 답이 된다.
        answer = transformToRightString(p);
        
        return answer;
    }
    
    // 올바른 문자열인지 확인
    public boolean isRightString(String p) {
        // 시작부터 ')' 이거나, p.length()가 0, 1이면 일단 올바른 문자열은 아니다. 바로 리턴
        if(p.charAt(0) == ')' || p.length() < 2) return false;
        
        Stack<Character> stack = new Stack<>();
        stack.add('(');
        
        for(int i=1; i<p.length(); i++) {
            char c = p.charAt(i);
            if(c == '(') { // 같으면 stack에 넣는다.
                stack.add(c);
                continue;
            }
            
            // stack이 이미 비워져 있는데 ')'있다는건 올바른문자열이 아니라는 것. 바로 리턴
            if(stack.isEmpty()) return false; 
            
            stack.pop(); // 다르면 뺀다.
        }
        
        // 스택이 비워진 상태여야 올바른 문자열
        return stack.isEmpty();
    }
    
    // w를 u와 v로 나누는 함수
    public String[] devide_w_to_u_v(String w) { 
        String[] rtn = {"", ""}; // rtn[0] = u, rtn[1] = v 넣을거임
        
        if (w.length() == 0) return rtn;

        char put_in_stack = w.charAt(0);
        Stack<Character> stack = new Stack<>();
        stack.add(put_in_stack);
        
        int index = -1; // u가 끝난 지점을 담는 index 값
        
        for(int i=1; i<w.length(); i++) {
            char c = w.charAt(i);
            
            if(stack.isEmpty()) { // stack이 이미 비워져 있는 상태이면 바로 반복문 종료
                index = i;
                break;
            }
            
            if(c == put_in_stack) { // 같으면 stack에 넣는다.
                stack.add(c);
                continue;
            }
                        
            stack.pop(); // 다르면 뺀다.
        }
        
        if(index < 0) {
            rtn[0] = w;
            rtn[1] = "";

            return rtn;
        }
            
        rtn[0] = w.substring(0, index); // u
        rtn[1] = w.substring(index);
                
        return rtn;
    }
    
    // 올바른 문자열로 변환하는 함수
    public String transformToRightString(String w) {
        if (w.length() == 0) return w; // 빈 문자열이면 그대로 반환.
        
        String rtn = "";
        
        // w를 u, v로 분리한다.
        String[] u_v = devide_w_to_u_v(w); // return string[2] u와 v
        
        String u = u_v[0];
        String v = u_v[1];

        
        String new_v = transformToRightString(v); // v를 재귀 함수에 넣은 결과
        boolean isRightU = isRightString(u); 
        if(isRightU) { // u 가 올바른 문자열이라면
            rtn = u + new_v;
            return rtn;
        }
        
        
        // u가 올바르지 않았던 문자열일 경우
        rtn = "(";
        rtn += new_v;
        rtn += ")";
        
        if(u.length() > 2) {
            String tmp = "";
            for(int i=1; i<u.length()-1; i++) { // 맨앞, 맨뒤 char 제외하고 뒤집어서 출력할 수 있게
                char tmp_c = u.charAt(i);
                if(tmp_c == '(') {
                    tmp += ")";
                    continue;
                }
                tmp += "(";
            }
            rtn += tmp;
        }
        
        return rtn;
    }
}