[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 괄호변환

문제보기

문제에서 이미 풀이법을 설명하고 있으므로 그대로 구현만 해주시면 됩니다

import java.util.Stack;

class Solution {
    
// 문자열을 받아 처리결과를 반환하는 메서드
    static String go(String w){
    	// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
        if(w.equals("")) return ""; 
        
	// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 
	//단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

        int len = w.length();
        
        int index = -1;
        int left = 0;
        int right = 0;
        
	// 균형잡힌 문자열로 분리해봅시다. '('의 갯수와 ')' 갯수가 일치하게 되는 시점까지 잘라서 u를 만들어주면 됩니다.
        for(int i = 0 ; i < len ; i++ ){
            if(w.charAt(i) == '('){
                left++;
            }else{
                right++;
            }
            if(left == right){
                index = i;
                break;
            }
        }
        
        String u = w.substring(0, index+1);
        String v = w.substring(index+1); // 나머지는 v가 됩니다.
        

	// 3. 문자열 u가 올바른 문자열인지 판단합니다 
        Stack<Integer> st = new Stack<>(); // '('가 있으면 스택에 넣고, ')'가 있으면 스택에서 뺌
        boolean goodStr = true; // 올바른지 여부를 판단 

        for(int i = 0 ; i < index+1 ; i++){
            if(u.charAt(i) == '('){
                st.push(1);
            }else{
                if(st.size() == 0){
                    goodStr = false; // 더이상 뺄게 없는데 ')'가 있다는것은 올바른 문자열이 아니란 얘기
                    break;
                }else{
                    st.pop();
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        if(goodStr){
	// 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  	// 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
            sb.append(u + go(v));
        }else{
        	// 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
	 	// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  		// 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
 		// 4-3. ')'를 다시 붙입니다. 
            sb.append("(" + go(v) + ")");

		//  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
            for(int i = 1 ; i < index ; i++){
                if(u.charAt(i) == '('){
                    sb.append(")");
                }else{
                    sb.append("(");
                }
            }
        }
       	//  4-5. 생성된 문자열을 반환합니다.
        return sb.toString();
    }
    
    public String solution(String p) {
        
        return go(p);
    }
}