프로그래머스 괄호변환

https://programmers.co.kr/learn/courses/30/lessons/60058
LEVEL2에 있는 문제였지만 알고리즘 자체만 보면 절대 여기있을 수준의 문제가 아닌거 같다.. ㅠㅠ

코딩테스트 연습 - 괄호 변환

 

 

 

먼저 문제에 제시된 알고리즘을 차근차근 따라가기위해 괄호가 균형을 이룬 경우와 올바른 경우를 확인해주는 두가지 함수를 boolean 타입으로 만들었다.

for문을 이용하여 가장 짧은 균형을 이룬 두 문자열이 나오면 다시 두 문자열을 비교하지않게 boolean변수 done을 두고 체크하였다.

 

 

여기까지는 잘왔는데.. 문자가 올바른 경우 재귀호출을 떠올리지 못해서 시간이 조금 더 걸렸다. 같은 행위를 더 작은 것에 대해 다시 수행하는 방법에 재귀가 있다는 것을 꼭 기억해야겠다고 다짐했다. 재귀로 문제를 해결해야한다는 것을 알게 된 후에 빠르게 StringBuilder를 이용해서 뒤집는 부분을 가볍게 (?) reverse()를 이용해 문제를 해결했다고 생각했지만 자꾸 테스트 케이스의 절반 정도가 틀렸다...ㅠ 알고보니 문자열 자체를 뒤집는게 아니라 괄호를 반대방향으로 해주는 것이었다. 항상 문제를 풀다가 하나가 막히고 그 막힌 것을 해결한 뒤에는 다급하게 해결하려는 경향이 있는 것 같다. 조금 더 신중하게 문제를 천천히 풀어야겠다.

 

 

 

 

 

 

풀이

package lv2;
import  java.util.*;
public class 괄호변환 {
    public static void main(String[] args) {
        String s = "()))((()";
        System.out.println(solution(s));
    }
    public static String solution(String p) {

        if(p.length()==0) return "";
        if(isRight(p)) return p;
        String answer = "";
        int size = p.length();
        String u = "";
        String v = "";
        String temp = "";
        boolean done = false;
        for(int i=1;i<=size;i++)
        {
            String target = p.substring(0,i);
            if(!done&&isBalanced(target)){
                done = true;
                u = target;
                v = p.substring(i);
                if(isRight(u)){
                    v=solution(v);
                   return u+v;
                }
                else{
                   answer+="(";
                   answer+=solution(v);
                   answer+=")";
                   u = u.substring(1,u.length()-1);
                   for(int j=0;j<u.length();j++){
                       if(u.charAt(j)=='(')  answer+=")";
                       else answer+="(";
                   }

                }
            }

        }
        return answer;
    }
    static boolean isRight(String s){
        int cnt1 = 0;
        int cnt2 = 0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='('){
              cnt1++;
            }
            else{ // ')'인 경우
                cnt2++;
            }
            if(cnt2>cnt1) return false;

        }
        return cnt1==cnt2;
    }
    static boolean isBalanced(String s){
        int cnt1=0, cnt2 = 0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(') cnt1++;
            else cnt2++;
        }
        return cnt1==cnt2;
    }
}