카카오 프로그래머스 / 괄호 변환/ 재귀/ JAVA

완성한 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String str = "()))((()";
        System.out.println(recurCheck(str));
    }

    static //올바른 괄호 문자열인지 검사하는 함수
    boolean isRight(String str) {
        int count = 0;
        boolean isRight = true;

        for(int i = 0 ; i < str.length(); i++) {
            if(str.charAt(i) == '(')
                count++;
            else
                count--;

            if(count < 0 ) {
                isRight = false;
            }
        }
        return isRight;
    }

    //최초의 균형잡힌 문자열의 인덱스를 반환하는 함수
    public static int firstBalance(String str) {
        int count = 0;

        for(int i = 0 ; i < str.length(); i++) {
            if(str.charAt(i) == '(')
                count++;
            else
                count--;

            if(count == 0 ) {
                return i;
            }
        }

        return -1;
    }

    //재귀로 문자열 괄호 검사를 수행
    public static String recurCheck(String str) {
        String u = "";
        String v = "";
        String resultStr = "";

        if(isRight(str)) 
            return str;
        else {
            //u와 v를 분리시켜줍니다.
            if(str.length() >= 2) {
                u += str.substring(0, firstBalance(str) +1);
                v += str.substring(firstBalance(str) + 1, str.length());
            }

            //u가 올바른 문자열일 경우
            if(isRight(u)) {
                return u + recurCheck(v);
            }else { //u가 올바른 문자열이 아닐 경우
                resultStr += "("+recurCheck(v)+")";
                u = u.substring(1 , u.length() - 1);//맨 앞 맨 뒤 자르고,

                StringBuilder newU = new StringBuilder(u);
                for(int i = 0; i < u.length(); i++) {
                    if(u.charAt(i)=='(') {
                        newU.setCharAt(i, ')');
                    }else {
                        newU.setCharAt(i, '(');
                    }
                }
                resultStr += newU.toString();
                return resultStr;
            }
        }
    }
}

해당 문자열이 올바른 문자열인가 확인하는 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
            String str = ")(";
            int count = 0;
            boolean isRight = true;

            //올바른 괄호 문자열인지 검사하는 코드
            for(int i = 0 ; i < str.length(); i++) {
                if(str.charAt(i) == '(')
                    count++;
                else
                    count--;
                if(count < 0 ) {
                    isRight = false;
                }
            }

            System.out.println("테스트결과 : "+ isRight); //false
    }

}

문자열이 올바른지 확인하기 위해서는 짝이 항상 맞는 상태여야하는데, count가 음수가 된다는 것은 )가 나대서 (보다 먼저 더 많이 나온 것이므로 false가 된다.

문자열이 올바른 문자열이면 그대로 출력해주면 된다.

public static void main(String[] args) {
        String str = "()))((()";
        System.out.println(recurCheck(str)); //이렇게 호출을 했을 때
    }
public static String recurCheck(String str) {
        if(isRight(str)) //올바른 문자열이면 
            return str;//그대로 출력
            }

하지만 올바른 문자열이 아닐 경우

else {
            //u와 v를 분리시켜줍니다.
            if(str.length() >= 2) {
                u += str.substring(0, firstBalance(str) +1);
                v += str.substring(firstBalance(str) + 1, str.length());
            }

u와 v로 문자열을 나눠주는데, u는 최초로 나오는 균형잡힌문자열이므로, ()가 짝이 맞는 순간까지 잘라서 저장시켜주면 된다.
이를 일기 위해 firstBalance함수를 만들었다.

//최초의 균형잡힌 문자열의 인덱스를 반환하는 함수
    public static int firstBalance(String str) {
        int count = 0;

        for(int i = 0 ; i < str.length(); i++) {
            if(str.charAt(i) == '(')
                count++;
            else
                count--;

            if(count == 0 ) {
                return i;
            }
        }

        return -1;
    }

밸런스가 맞는 최초의 순간 str의 인덱스 값을 반환한다. 이걸로 u랑 v를 만들면

//u가 올바른 문자열일 경우
            if(isRight(u)) {
                return u + recurCheck(v);
            }

u가 올바른 문자열인지 확인 후, 올바르면 v에 대해서도 똑같이 검사를 해준다.
하지만 u부터 올바르지 않았을 경우

else { //u가 올바른 문자열이 아닐 경우
                resultStr += "("+recurCheck(v)+")";
                u = u.substring(1 , u.length() - 1);//맨 앞 맨 뒤 자르고,

                StringBuilder newU = new StringBuilder(u);
                for(int i = 0; i < u.length(); i++) {
                    if(u.charAt(i)=='(') {
                        newU.setCharAt(i, ')');
                    }else {
                        newU.setCharAt(i, '(');
                    }
                }
                resultStr += newU.toString();
                return resultStr;
            }

결과 문자열에 ( v를 고친 문자열 ) 로 넣어주고 해주고
u의 앞 뒤를 자른 뒤(주어지는 문자열이 균형잡힌 문자열이기 때문에 맨 앞 맨 뒤는 반드시 (과 ) 한 쌍이 들어있다. 하지만 결과 문자열에 (와 )를 써주었으므로 없애준다.)

남은 u에 (가 있으면 )로 바꿔주고 )가 있으면 (로 바꿔준다.
그리고 이를 결과 문자열 맨 끝에 붙이면
괄호가 올바르게 고쳐진다.