괄호 변환 (2020 KAKAO BLIND RECRUITMENT)

원본 : https://programmers.co.kr/learn/courses/30/lessons/60058

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

 

풀이

class Solution {
    public String solution(String p) {
        return fn(p);
    }

    public String fn (String str) {
        if (str.isEmpty()) {
            return "";
        }

        String[] arr = balance(str);
        String u = arr[0];
        String v = arr[1];

        if (isComplete(u)) {
            return u + fn(v);
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append("(");
            sb.append(fn(v));
            sb.append(")");

            u = u.substring(1, u.length() - 1);

            for (char chu : u.toCharArray()) {
                if (chu == '(') {
                    sb.append(")");
                } else {
                    sb.append("(");
                }
            }

            return sb.toString();
        }
    }

    public String[] balance(String str) {
        int cnt = 0;
        boolean flag = true;
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();

        for (char ch : str.toCharArray()) {
            if (ch == str.charAt(0)) {
                cnt++;
            } else {
                cnt--;
            }

            if (flag) {
                sb1.append(ch);
            } else {
                sb2.append(ch);
            }

            if (flag && cnt == 0) {
                flag = false;
            }
        }

        return new String[]{sb1.toString(), sb2.toString()};
    }

    public boolean isComplete(String str) {
        int cnt = 0;

        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                cnt++;
            } else {
                cnt--;
            }

            if (cnt < 0) {
                return false;
            }
        }

        return true;
    }
}