[알고리즘] [2020 카카오 블라인드] 괄호 변환

1. 문제

문제를 딱 보면 엄청나게 많은 조건들이 있다. 사람은 한번에 여러가지를 기억하지 못하기 때문에 조건을 이해하는데 시간이 오래 걸렸다.

2. 나의 풀이

문제를 봤을 때 재귀를 이용하는 문제라는 것을 알았다. 우선 문제의 조건대로 주어진 문자열의 길이가 0일 경우 빈 문자열을 반환하게 하고, 현재 문자열이 올바른 괄호 문자열일 경우 해당 문자열을 그대로 반환했다.

 

또한 문자열 u는 균형잡힌 괄호 문자열이므로 문자열 w를 u와 v로 나누어주는 getBalanceIndex() 메서드를 만들어 주었다. 여기서 return할 때 1을 더해주어 문자열 u와 v를 구분하는 인덱스를 구한다.

 

그리고 u가 올바른 괄호 문자열일 경우는 문자열 u에 v를 다시 나누는 재귀함수를 호출해서 더해준다.

 

u가 올바른 괄호 문자열이 아닌 경우 주어진 조건대로 v를 재귀함수로 호출하고 u는 맨앞, 맨뒤 문자를 삭제해서 반대 괄호로 바꿔주는 reverse를 호출해준다. 이때 주의할점으로는 u는 좌우 대칭이 아닐 수 있기 때문에 직접 바꿔줘야한다.

import java.util.*;


class Solution {
    
    String answer = "";

    public String solution(String p) {
        int balanceIndex = getBalanceIndex(p);
        answer = recursive(p, balanceIndex);
        System.out.println(answer);
        return answer;
    }

    public String recursive(String p, int balanceIndex){

        if(p.length() == 0) {
            return "";
        } else if(isCorrectBracket(p)){
            return p;
        }

        String u = p.substring(0,balanceIndex);
        String v = p.substring(balanceIndex);
        int nextBalanceIndexV = getBalanceIndex(v);

        if(isCorrectBracket(u)){
            return u + recursive(v,nextBalanceIndexV);
        } else{
            return "(" + recursive(v,nextBalanceIndexV) + ")" + reverse(u.substring(1,u.length()-1));
        }
    }

    public int getBalanceIndex(String sub){
        int i;
        int n1 = 0;
        int n2 = 0;
        for(i=0;i<sub.length();i++){
            if(sub.charAt(i) == '(')
                n1++;
            else
                n2++;
            if(n1 == n2)
                return i+1;
        }
        return i;
    }

    public String reverse(String sub){
        StringBuffer sb= new StringBuffer();
        for(int i=0;i<sub.length();i++){
            String w = String.valueOf(sub.charAt(i));
            if("(".equals(w))
                sb.append(")");
            else
                sb.append("(");
        }
        return sb.toString();
    }

    public boolean isCorrectBracket(String w){
        int count = 0;
        for(int i = 0 ; i < w.length(); i++) {
            if(w.charAt(i) == '(') {
                count++;
            }else
                count--;
            if(count < 0)
                return false;
        }
        return count == 0;
    }
    
}