괄호 변환 - '2020 카카오 코딩 테스트'

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

주어진 괄호 문자열을 정상적인 문자열로 반환 하는 문제 입니다. 문제에서는 '올바른 괄호 문자열'과 '균형 잡힌 괄호 문자열'로 용어를 나누어 설명 합니다. 문제에서 제시한 방법대로 그대로 구현 하면 되는 문제 입니다. 따라서, 문제를 꼼꼼히 읽어 보는게 중요 했던거 같습니다. 사실, 문제의 설명이 잘이해가 가지 않았지만, 그냥 설명대로 구현했더니, 통과 할수 있었습니다.

 

public class Page346 {
    /*
    * p             result
    * "(()())()"    "(()())()"
    * ")("          "()"
    * "()))((()"    "()(())()"
    */
    public static void main(String[] args) {
        String p = "()))((()";
        System.out.print(new Page346().solution(p));
    }

    public String solution(String p) {
        return getCorrectStr(p);
    }

    private String getCorrectStr(String p) {
        // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환 합니다.
        if (p.equals("")) return p;

        // p가 '올바른 문자열' 이면 그냥 반환
        if (isCorrectStr(p)) return p;

        // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
        String[] uAndV = getBalancedStrs(p);
        String u = uAndV[0];
        String v = uAndV[1];

        // 3. 문자열 u가 '올바른 괄호 문자열' 이라면 문자열 v에 대해 1단계부터 다시 수행.
        if (isCorrectStr(u)) {
            return u + getCorrectStr(v);
        } else {
            // 4. 문자열 u가 '올바른 괄호 문자열'이 아니라면 아래 과정을 수행
            // 4-1. 빈 문자열에 첫번쨰 문자로 '('를 붙입니다.
            String str = "(";
            // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
            str += getCorrectStr(v);
            // 4-3. ')'를 다시 붙입니다.
            str += ')';
            // 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
            char[] chars = u.toCharArray();
            String resultStr = "";
            // 4-4. 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
            for (int i = 1; i < chars.length-1; i++) {
                if (chars[i] == '(') {
                    resultStr += ')';
                } else if (chars[i] == ')') {
                    resultStr += '(';
                }
            }
            str += resultStr;

            // 4-5. 생성된 문자열을 반환합니다.
            return str;
        }
    }

    private boolean isCorrectStr(String p) {
        char[] chars = p.toCharArray();
        int openBracketCnt = 0;
        int closeBracketCnt = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(')
                openBracketCnt++;
            else
                closeBracketCnt++;

            if (closeBracketCnt > openBracketCnt) return false;
        }
        return true;
    }

    private String[] getBalancedStrs(String p) {
        char[] chars = p.toCharArray();
        int openBracketCnt = 0;
        int closeBracketCnt = 0;
        int boundaryIdx = p.length() - 1;

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(')
                openBracketCnt++;
            else
                closeBracketCnt++;

            if (openBracketCnt == closeBracketCnt) {
                boundaryIdx = i;
                break;
            }
        }

        String u = p.substring(0, boundaryIdx + 1);
        String v = p.substring(boundaryIdx + 1);
        return new String[]{u, v};
    }
}

 

 

private boolean isCorrectStr(String p) {
        char[] chars = p.toCharArray();
        int openBracketCnt = 0;
        int closeBracketCnt = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(')
                openBracketCnt++;
            else
                closeBracketCnt++;

            if (closeBracketCnt > openBracketCnt) return false;
        }
        return true;
    }

isCorrectStr() 메서드의 경우는 첫번째 인덱스 부터 문자열 끝까지 탐색 하면서, 열려있는 괄호의 갯수 보다 닫혀있는 괄호의 갯수가 더 많아지면 올바르지 못한 괄호 문자열 이라고 생각하고 구현 하였습니다.