[프로그래머스 / Level2] 괄호 변환 (Java)

문제 보기

사용한 것

• top-down을 사용하여 괄호 집합을 올바른 괄호 집합으로 변환

풀이 방법

• 문제에서 풀이 방법을 설명하고 있다. 따라서 구현만 해주면 된다.
  • 하나의 괄호 집합은 '('의 수와 ')'의 수가 같아질 때 이다.
  • 올바르지 않은 괄호 집합은 ')'가 '('보다 먼저 나오는 경우이다.

코드

class Solution {

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

    String dp(String p) {
        if (p.equals("")) {
            return p;
        }

        String u = "";
        String v = "";
        int num1 = 0;
        int num2 = 0;
        int idx = 0;
        boolean illegal = false;

        while (idx < p.length()) {
            char c = p.charAt(idx);

            if (c == '(') {
                num1++;
            } else {
                if (num1 == 0) {
                    illegal = true;
                }
                num2++;
            }

            u += c;
            idx++;

            if (num1 != 0 && num1 == num2) {
                break;
            }
        }

        while (idx < p.length()) {
            v += p.charAt(idx++);
        }

        if (illegal) {
            String fixed = "(" + dp(v) + ")";
            for (int i = 1; i < u.length() - 1; i++) {
                char c = u.charAt(i);
                if (c == '(') {
                    fixed += ")";
                } else {
                    fixed += "(";
                }
            }

            return fixed;
        } else {
            return u + dp(v);
        }
    }
}