괄호변환 [프로그래머스]

1) 문제 접근 방법

- 문제의 조건에 따라, 재귀함수를 구현해서 문제를 해결했다.

- 문자열 w를 두 균형잡힌 문자열 u, v로 분리해야 하는데, 

  이 때, open과 close의 길이가 일치할 때를 기준으로 판단해줬다 

- u, v로 분리한 이후에는, u가 '올바른 괄호 문자열'인지를 판단해줬다. 

  이를 위한 isRight 메소드를 선언했다. 

- isRight 메소드는 스택을 통해서 올바른 괄호 문자열인지 판단해줬다 

- u가 올바른 괄호 문자열이라면 3-1에 따라 재귀를 수행하고, 

  아니라면 4에 따라 작업을 수행했다

- 4를 수행하는 과정에서 getNewU라는 메소드를 통해서 새로운 u를 구해서 반환했다. 

 

2) 소스 코드

import java.util.*; 

class Solution {
    
    public boolean isRight(String u){
        
        Stack<Character> stk = new Stack<>();
        
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i) == '('){
                stk.push('(');
            }else{
                if(stk.size() == 0){
                    return false;
                }
                stk.pop();
            }
        }
        
        if(stk.size() == 0){
            return true;
        }
        
        return false;
        
        
    }
    
    public String getNewU(String u){
        int uLen = u.length(); 
        String tmp = u.substring(1, uLen-1);
        String ans = "";
        
        for(Character c: tmp.toCharArray()){
            if(c == '('){
                ans += Character.toString(')');
            }else{
                ans += Character.toString('(');
            }
        }
        
        return ans; 
        
    }
    
    
    public String recursive(String p){
        
        if(p.equals("")){
            return "";
        }
        
        int open = 0;
        int close = 0;
        String u = "";
        String v = "";
        
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i) == '('){
                open += 1;
            }else{
                close += 1;
            }
            
            if(open == close){
                u = p.substring(0, i+1);
                v = p.substring(i+1);
                
                boolean res = isRight(u);
            
                if(res){
                    return u + recursive(v);
                }else{
                    break;
                }
            }
            
            
        }
        
        
        String tmp = "";
        tmp += Character.toString('(');
        tmp += recursive(v);
        tmp += Character.toString(')');
        tmp += getNewU(u);
        return tmp; 
        
        
        
    }
    
    
    
    public String solution(String p) {
        String answer = "";
        
        if(p.equals("")){
            return answer;
        }
        
        answer = recursive(p);
        
        
        return answer;
    }
}

 

3) 소스 코드 리팩토링

- open==close일 때, break 한후에, for문 바깥에서 처리를 해줬다.

import java.util.*; 

class Solution {
    
    public boolean isRight(String u){
        
        Stack<Character> stk = new Stack<>();
        
        for(int i=0; i<u.length(); i++){
            if(u.charAt(i) == '('){
                stk.push('(');
            }else{
                if(stk.size() == 0){
                    return false;
                }
                stk.pop();
            }
        }
        
        if(stk.size() == 0){
            return true;
        }
        
        return false;
        
        
    }
    
    public String getNewU(String u){
        int uLen = u.length(); 
        String tmp = u.substring(1, uLen-1);
        String ans = "";
        
        for(Character c: tmp.toCharArray()){
            if(c == '('){
                ans += Character.toString(')');
            }else{
                ans += Character.toString('(');
            }
        }
        
        return ans; 
        
    }
    
    
    public String recursive(String p){
        
        if(p.equals("")){
            return "";
        }
        
        int open = 0;
        int close = 0;
        int pos = 0; 
        String u = "";
        String v = "";
        
        for(int i=0; i<p.length(); i++){
            if(p.charAt(i) == '('){
                open += 1;
            }else{
                close += 1;
            }
            
            if(open == close){
                pos = i;
                break;
            }
        }
        
        
        u = p.substring(0, pos+1);
        v = p.substring(pos+1);
                
        boolean res = isRight(u);
            
        if(res){
            return u + recursive(v);
        }else{
            String tmp = "";
            tmp += Character.toString('(');
            tmp += recursive(v);
            tmp += Character.toString(')');
            tmp += getNewU(u);
            return tmp; 
        }
        
        
        
        
        
    }
    
    
    
    public String solution(String p) {
        String answer = "";
        
        if(p.equals("")){
            return answer;
        }
        
        answer = recursive(p);
        
        
        return answer;
    }
}