프로그래머스 - 괄호 변환

괄호 변환 : https://programmers.co.kr/learn/courses/30/lessons/60058

Problems

---

Solves

주어진 변환 알고리즘을 사용하면 해결할 수 있는 문제.
문자열 w를 "균형잡힌 괄호 문자열" u,v 로 나누는 함수 stringSeparate와 해당 문자열이 "올바른 괄호 문자열"인지 판단하는 isCorrect함수를 이용해서 구현했다.

먼저 stringSeparte는 문자열 w를 매개변수로 받아서 더 이상 "균형잡힌 괄호 문자열"로 나눌수 없는 u문자열과 나머지 문자열 v로 나누어준다.
"균형잡힌 괄호 문자열"은 '('과 ')'의 갯수가 같은 문자열이기 때문에 w의 첫번째 문자부터 '('과')'의 갯수가 같을 때 까지 stack에 저장해서 u를 만들고 나머지 index를 이용해 v를 만들어준다.
그리고 난 후 stack에 저장된 u의 문자열의 "올바른 괄호 문자열"여부를 판단하고 맞다면 3번 조건을 수행.
다르다면 4번 조건을 수행해준다.
그런 다음 새로 생성된 문자열을 반환해주면 최종적으로 stringSeparte에서는 "올바른 괄호 문자열"을 반환하게 된다.

---

Code

import java.util.Stack;
class Solution {
    public String solution(String p) {
        
        String answer = stringSeparate(p);
        return answer;
    }
    
    //문자열을 u,v로 분리하여 "올바른 괄호 문자열"을 반환하는 함수
    public String stringSeparate(String s){
    	//빈 문자열이 매개변수로 들어오게 되면 그대로 반환
        if(s == "") return s;
        
        Stack<Character> stack = new Stack<>();
        int leftCount=0;
        int rightCount=0;
        String u = "";
        String v = "";
        //해당 문자열을 돌면서 leftCount('('의 갯수)와 rightCount(')'의 갯수)가 같아지면 "균형잡힌 괄호 문자열" 조건을 만족하게 된다.
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c == '('){
                leftCount++;
            }else{
                rightCount++;
            }
            stack.push(c);
            
            //leftCount == rightCount 조건을 만족하게 되면 u,v를 갱신 해준다.
            if(leftCount == rightCount){
                for(int j=0;j<stack.size();j++){
                    u+=stack.get(j);
                }
                //i의 다음 index가 해당 문자열을 벗어나지 않았다면 v에 나머지 문자열을 초기화
                //해당 문자열 범위를 벗어났다면 빈 문자열
                if(i+1<s.length()){
                    v = s.substring(i+1);   
                }
                break;
            }
        }
        
        //u에 저장된 문자열이 "올바른 괄호 문자열"이라면 3번 조건에 따른다.
        if(isCorrect(stack)){
            return u+stringSeparate(v);
        }
        //"올바른 괄호 문자열"이 아니라면 4번 조건을 따른다.
        else{
            StringBuilder sb = new StringBuilder();
            //4-1. 빈 문자열에 첫 번쨰 문자로 '('를 붙인다.
            sb.append("(");
            //4-2. 문자열 v에 대한 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.
            sb.append(stringSeparate(v));
            //4-3. ')'를 다시 붙인다.
            sb.append(")");
            //4-4. u의 첫번째와 마지막 문자를 제거
            String temp = u.substring(1, u.length()-1);
            //4-4. 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.
            for(char t : temp.toCharArray()){
                if(t == ')') sb.append("(");
                else if(t == '(') sb.append(")");
            }
            //4-5. 생성된 문자열을 반환
            return sb.toString();
        }
    }
    
    /*
    "올바른 괄호 문자열"의 조건은 '('과 ')'의 갯수가 같고 짝이 맞아야한다. 그렇기 때문에 맨 첫번째 문자는 '(', 맨 마지막 문자는 ')'가 올수 밖에 없다.
    그리고 해당 함수의 파라미터는 u문자열의 문자가 들어있는 stack이 들어오게 되는데, u문자열은 더 이상 "균형잡힌 괄호 문자열"로 나눌수 없는 문자열이기 때문에 "()()"이런 식으로 첫번째와 마지막 문자를 제거했을때 괄호의 짝이 맞지 않는 경우가 올 수 없기 때문에 해당 조건이 성립할수 있다.
    */
    boolean isCorrect(Stack<Character> stack){
        if(stack.get(0) == '(' && stack.get(stack.size()-1) == ')') return true;
        return false;
    }
}

---

Result