[2020 KAKAO BLIND RECRUITMENT] 괄호 반환

[2020 KAKAO BLIND RECRUITMENT] 괄호 반환

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

용어의 정의

 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라 고 부른다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부른다. 예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아니다. 반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 이다. '(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열 로 변환할 수 있다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리한다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다.

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행한다.

    3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환한다.

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면

    4-1. 빈 문자열에 첫 번째 문자로 '('을 붙인다.

    4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다.

    4-3. ')'를 다시 붙인다.

    4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다.

    4-5. 생성된 문자열을 반환한다.

 

 이러한 구현 절차를 주고, 절차대로 구현하는 문제이다. 처음 이 문제를 접했을 때 긴 텍스트의 양을 보고 살짝 겁을 먹었다. 다행히 절차 그대로 구현만 하면 되는 문제였다. 

 

public class ParenthesisConversion {

    static boolean isCorrectParenthesis(String parenthesis) {
        int count = 0;
        for (char c : parenthesis.toCharArray()) {
            if (c == '(') ++count;
            else if (c == ')') --count;

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

    static String getCorrectParenthesis(String parenthesis) {

        /** 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다. */
        if (parenthesis.equals("")) {
            return parenthesis;
        } else {
            /** 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리한다.
             * 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다. */
            int count = 0, index = 0;
            for (int i = 0; i <= parenthesis.length(); i++) {
                if (parenthesis.charAt(i) == '(') ++count;
                else if (parenthesis.charAt(i) == ')') --count;
                if (count == 0) {
                    index = i;
                    break;
                }
            }
            String u = parenthesis.substring(0, index + 1);
            String v = parenthesis.substring(index + 1);

            /** 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행한다. */
            if (isCorrectParenthesis(u)) {
                /** 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환한다. */
                return u + getCorrectParenthesis(v);
            } else { /** 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면  */
                /** 4-1. 빈 문자열에 첫 번째 문자로 '('을 붙인다. */
                StringBuilder stringBuilder = new StringBuilder("(");
                /** 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다. */
                stringBuilder.append(getCorrectParenthesis(v));
                /** 4-3. ')'를 다시 붙인다. */
                stringBuilder.append(")");

                /** 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다. */
                for (int i = 1; i < u.length() - 1; i++) {
                    if (u.charAt(i) == '(') {
                        stringBuilder.append(")");
                    } else if (u.charAt(i) == ')') {
                        stringBuilder.append("(");
                    }
                }

                /** 4-5. 생성된 문자열을 반환한다. */
                return stringBuilder.toString();
            }
        }
    }

    static String solution(String p) {
        String answer = getCorrectParenthesis(p);

        return answer;
    }

    public static void main(String[] args) {
        String[] inputs = {
                "(()())()",
                ")(",
                "()))((()"
        };

        for (String p : inputs) {
            System.out.println(solution(p));
        }
    }
}

 

 문제 풀이가 어렵진 않았지만, 문제 이해 자체가 어려워서 코드를 상당 부분 참고 하였다. 만약 추가적인 절차가 없었더라면 풀이를 시도조차 하지 못했을 것 같다. 교수님의 풀이를 보며 코드를 좀 더 수정해보았다.

 

public class ParenthesisConversion_1 {

    static boolean isCorrectParenthesis(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            count += (c == '(') ? 1 : -1;
            if (count < 0) return false; // 올바른 괄호는 절대 음수가 나올 수 없다.
        }
        return count == 0;
    }

    static String getCorrectParenthesis(String parenthesis) {

        /** 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환한다. */
        if (parenthesis.equals("")) {
            return parenthesis;
        } else {
            /** 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리한다.
             * 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있다. */
            int count = 0, index = 0;
            for (int i = 0; i <= parenthesis.length(); i++) {
                count += (parenthesis.charAt(i) == '(') ? 1 : -1;
                if (count == 0) {
                    index = i;
                    break;
                }
            }
            String u = parenthesis.substring(0, index + 1);
            String v = parenthesis.substring(index + 1);

            /** 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행한다. */
            if (isCorrectParenthesis(u)) {
                /** 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환한다. */
                return u + getCorrectParenthesis(v);
            } else { /** 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면  */
                /** 4-1. 빈 문자열에 첫 번째 문자로 '('을 붙인다. */
                StringBuilder stringBuilder = new StringBuilder("(")
                        /** 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙인다. */
                        .append(getCorrectParenthesis(v))
                        /** 4-3. ')'를 다시 붙인다. */
                        .append(")")
                        /** 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다. */
                        .append(new StringBuilder(u)
                                .deleteCharAt(u.length() - 1)
                                .deleteCharAt(0)
                                .toString()
                                .replace('(', '_')
                                .replace(')', '(')
                                .replace('_', ')'));

                /** 4-5. 생성된 문자열을 반환한다. */
                return stringBuilder.toString();
            }
        }
    }

    static String solution(String p) {
        String answer = getCorrectParenthesis(p);

        return answer;
    }

    public static void main(String[] args) {
        String[] inputs = {
                "(()())()",
                ")(",
                "()))((()"
        };

        for (String p : inputs) {
            System.out.println(solution(p));
        }
    }
}

 

 가장 크게 변화된 부분은 StringBuilder와 replace를 활용하여 문자열 swap을 진행하였다. 다양하게 활용 가능 할 것 같다.

 

references.

소프트웨어공학과 이승진 교수님의 특강자료를 기반으로 작성된 게시글입니다.