프로그래머스 - 올바른 브라켓 만들기

어렵게 생각하니 어렵고 쉽게 생각하니 쉽다라는 건 이 문제를 두고 말하는 듯하다.

알고리즘 자체를 써두었고, "재귀"라는 말을 썼으니 재귀적으로 해결하면 되는데

머리속에서 이해가 안되면 선뜻 코딩하기가 어려웠다.

 

 

스택을 재귀로 바꿔도 되겠지만, 가독성을 위해 스택을 사용했다.

import java.util.Stack;

public class SkillTestLevel2_2 {

    private final char open = '(', close = ')';

    private int findUnbalanceIndex (String p) {

        char[] data = p.toCharArray();
        int balanceCnt = 0;
        for (int i = 0; i < data.length; i++) {

            if (data[i] == open)
                balanceCnt++;
            else
                balanceCnt--;

            if (balanceCnt == 0)
                return i + 1;
        }
        return data.length;
    }

    private boolean isGoodBracket( char[] data ) {

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < data.length; i++) {
            if (data[i] != open) {
                if (stack.empty())
                    return false;
                else
                    stack.pop();
            } else {
                stack.push(open);
            }
        }
        return true;
    }

    public String solution(String p) {

        if (p.isEmpty())
            return p;

        char[] u = p.substring(0, findUnbalanceIndex(p)).toCharArray();
        char[] v = p.substring(findUnbalanceIndex(p)).toCharArray();

        if (isGoodBracket(u))
            return String.valueOf(u) + solution(String.valueOf(v));

        StringBuffer sbf = new StringBuffer(open);
        sbf.append(solution(String.valueOf(v)))
            .append(close);

        for (int i = 1; i < u.length - 1; i++)
            sbf.append(u[i] == open ? close : open);

        return sbf.toString();
    }

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

        // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
        // 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
        char[] u = p.substring(0, findUnbalanceIndex(p)).toCharArray();
        char[] v = p.substring(findUnbalanceIndex(p)).toCharArray();

        // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
        if (isGoodBracket(u))
            // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
            return String.valueOf(u) + solveCodeWithComment(String.valueOf(v));

        // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
        // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
        StringBuffer sbf = new StringBuffer(open);
        // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
        sbf.append(solveCodeWithComment(String.valueOf(v)))
                // 4-3. ')'를 다시 붙입니다.
                .append(close);

        // 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        for (int i = 1; i < u.length - 1; i++)
            sbf.append(u[i] == open ? close : open);

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