본문 바로가기
algorithm

[JAVA] 괄호변환 (kakao 2020)

by onejunu 2020. 7. 31.

 

문제

위 문제는 알고리즘을 다 제공하였다. 

 

그대로 구현만 하면 되는 아주 심플한 문제다. 여기서 String 을 자바로 어떻게 다룰 것인지가 문제인데

 

예를 들어 String p = "maple Story" 라는 String 이 있을 때, 각각의 char에 접근하는 방법은 몇가지 있는데 

 

1. charAt으로 접근하는 방법

for(int i=0;i<p.length();i++){
	p.charAt(i);
}

2. toCharArray 로 접근하는 방법이 있다.

for(char s : p.toCharArray()){
	
}

 

사실 다른 사람의 풀이를 보면서 2번의 방법이 있다는 것을 알았다...

 

본인은 지저분해 보일 수 있는 1번의 방법으로 문제를 풀었으나 보기에도 깔끔한 2번의 방법을 권장한다.

 

알고리즘은 위에 다 설명되어 있으니 코드만 업로드 하겠다.

 

import java.util.*;
class Solution {
    public String solution(String p) {
            return solve(p);
    }

    public static String solve(String w){
        if(w.length()==0) return w;
        String[] uv = splitUV(w); // uv[0] = u , uv[1] = v
        if(isRight(uv[0])){
            return uv[0] + solve(uv[1]);
        }
        else{
            String result = "(" + solve(uv[1]) + ")";
            return result + reverseString(uv[0]);

        }
    }

    public static String[] splitUV(String p){
        int flag =0;
        int splitLineIndex=0;
        for(int i=0;i<p.length();i++){
            if(p.charAt(i)=='('){
                flag++;
            }else{
                flag--;
            }
            if(flag==0){
                splitLineIndex = i+1;
                break;
            }
        }
        return new String[]{new String(p.substring(0,splitLineIndex)),
        new String(p.substring(splitLineIndex,p.length()))};
    }

    public static boolean isRight(String u){
        Stack<Character> stack = new Stack<>();

        for(int i=0;i<u.length();i++){
            if(u.charAt(i)=='('){
                stack.push('(');
            }else if(u.charAt(i)==')'){
                if(stack.empty()){
                    return false;
                }
                else{
                    stack.pop();
                }
            }
        }
        if(stack.empty()){return true;}
        return false;
    }

    public static String reverseString(String p){
        String ret = "";
        for(int i=1;i<p.length()-1;i++){
            if(p.charAt(i)=='('){ret += ")";}
            else{ret += "(";}
        }
        return ret;
    }


}

댓글