프로그래머스 - 괄호 변환(Java)

dfs 문제입니다.

'('와 ')'가 같은 개수로 주어졌을 때, 괄호가 올바르게 닫히도록 만드는 문제입니다.

 

구현 방법은 이미 문제 자체에 주어져 있습니다.

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. 생성된 문자열을 반환합니다.

정말 위에서 주어진 대로 구현하면 되는 문제입니다.

 

[구현 코드]

import java.util.Stack;

class Solution {
    public String solution(String p) {
        if (check(p)) return p;
        else return dfs(p);
    }

    // 올바른 문자열인지 확인
    private static boolean check(String s) {
        Stack<Character> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') st.add(c);
            else {
                if (st.isEmpty()) return false;
                else st.pop();
            }
        }

        if (!st.isEmpty()) return false;
        else return true;
    }

    private static String dfs(String s) {

        // 1
        if (s.length() == 0) return s;

        // 2
        String u = "", v = "";
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') cnt1++;
            else cnt2++;

            //균형잡힌 문자열일 때 u,v 분리
            if (((cnt1 > 0) && (cnt2 > 0)) && (cnt1 == cnt2)) {
                u = s.substring(0, i + 1);
                if (i < s.length() - 1) v = s.substring(i + 1, s.length());
                break;
            }

        }

        // 3
        if (check(u)) return u + dfs(v);
        else {
            // 4
            String tmp = "(" + dfs(v) + ")";
            u = u.substring(1, u.length() - 1);
            u = u.replace("(", ".");
            u = u.replace(")", "(");
            u = u.replace(".", ")");
            tmp = tmp + u;
            return tmp;
        }
    }
}