[2020 KAKAO BLIND RECRUITMENT] 괄호변환 (JAVA)

 

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

 

용어의 설명대로 재귀함수를 만들면 어렵지 않게 풀 수 있는 문제

 

 

public class 괄호변환 {
    public String solution(String p) {
        String answer = solve(p);
 
        return answer;
    }
 
    // 문자열 반환을 위한 재귀함수
    static String solve(String p) {
        
        // 입력받은 문자열이 빈 문자열이거나 '올바른 괄호 문자열'이면 바로 return
        if (p.isEmpty() || correct_paren(p))
            return p;
 
        String u = "", v = "";
 
        int i = 0, cnt = 0;
        for (; i < p.length(); i++) {
            u += p.charAt(i);
            cnt = p.charAt(i) == '(' ? cnt + 1 : cnt - 1;
            
            // '균형잡힌 괄호 문자열'이 만들어지면 분리를 멈춘다.
            if (cnt == 0) {
                i++;
                break;
            }
        }
 
        if (i != p.length())
            v = p.substring(i);
 
        String answer = "";
        String tmp = "";
        
        if (correct_paren(u)) { // u가 올바른 괄호 문자열이면
            tmp = solve(v);  // v에 대해 1단계부터 다시 수행하고 (1)
            answer += u + tmp;  // u와 (1)의 결과를 이어 붙인다.
        } else { // u가 올바른 괄호 문자열이 아니라면
            tmp += "("; // 빈 문자열에 '('를 붙이고
            tmp += solve(v); // v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙이고
            tmp += ")"; // ')'를 붙여준다.
 
            // u의 첫 번째 문자와 마지막 문자를 제거하고
            for (int j = 1; j < u.length() - 1; j++)
                tmp += u.charAt(j) == '(' ? ")" : "(";  // 나머지를 뒤집어서 뒤에 붙인다.
            answer = tmp;
        }
 
        return answer;
    }
 
    // 올바른 괄호 문자열인가를 판단하는 함수
    static boolean correct_paren(String p) {
        int total = 0;
 
        for (int i = 0; i < p.length(); i++) {
            char tmp = p.charAt(i);
 
            if (tmp == '(')
                total--;
            else
                total++;
 
            if (total > 0)
                return false;
        }
 
        if (total == 0)
            return true;
        return false;
    }
 
}