자바(JAVA) - 괄호 변환(Programmers : 12973)

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

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

오랜만에 올바른 접근으로 깔끔하게 풀어낸 문제였다.

조금 잘못 이해한 부분이 있어서 디버깅 중에 어려움이 있었지만 어렵지 않게 고칠 수 있었다.

 

dfs로 앞에서부터 한글자씩 붙여나가며 u가 "균형잡힌 괄호 문자열"인지 "올바른 괄호 문자열"인지 확인하고,

문제에 기재된 알고리즘을 적용한 뒤, base가 되는 string을 초기화, 동일한 스탭을 반복하여 정답을 찾을 수 있었다.

 

복잡한 입력값 ")()()(" 을 예로 dfs 호출 시 w, u , v의 값을 보면 :

 

ptr : 1  -  w : ")()()(" , u :  ")" , v : "()()(" 

ptr : 2  -  w : ")()()(" , u :  ")(" , v : ")()("   // "균형잡힌 괄호 문자열" 에 해당되므로 v에 대한 재귀 실행

      => ptr : 1  -  w : ")()(" , u :  ")" , v : "()("

      => ptr : 2  -  w : ")()(" , u :  ")(" , v : ")(" // "균형잡힌 괄호 문자열" 에 해당되므로 v에 대한 재귀 실행 

            => ptr : 1  -  w : ")(" , u :  ")" , v : "("

            => ptr : 2  -  w : ")(" , u :  ")(" , v : ""  // "균형잡힌 괄호 문자열" 에 해당되므로 v에 대한 재귀 실행

 

u가 "올바른 괄호 문자열"인 경우는 그냥 쪼개고 뒤에 남은  v에 진행하면 되는 반면, 

"균형잡힌 괄호 문자열"일 경우에는 v에 대한 재귀 결과값이 요구되며, 반환된 값을 "(", ")"으로 감싸준 뒤,

u의 앞뒤 값을 제거한 상태에서 모든 괄호의 위치를 반대로 바꿔준 값을 뒤에 붙여줘야한다.

 

위 예제의 경우 depth 3 - ptr : 2 를 보면 v 의 값이 "" 이며, 위 처리 과정으로 인해 "(" + "" + ")" = "()"가 반환되며, u의 경우 앞 뒤, 괄호를 제거하면 ""가 되므로 그대로 뒤에 붙게된다. 그러므로 "()" +  "" = "()" 을 반환.

반환된 값은 depth 2 - ptr : 2 에서 동일하게 괄호로 감싸 "(" + "()" + ")" + "" = "(())"가 되고,

동일하게 depth 1 - ptr : 2 에서 마지막으로 괄호로 감싸게 되어 최종 결과값은 "(" + "(())" + ")" + "" = "((()))"이 된다.

 

import java.util.*;
class Solution {
    String answer = "";
    public String solution(String p) {
        String w = p;
        
        answer = dfs(w, "", "", 0, "");
        return answer;
    }
    
    public String dfs(String w, String u, String v, int ptr, String completedStr) {
        int balanceType = getBalanceType(u);
        
        // "올바른 괄호 문자열"일 경우
        if(balanceType == 0) {
            completedStr += u;
            w = v;
            u = "";
            v = "";
            ptr = 0;
        // "균형잡힌 괄호 문자열"일 경우
        } else if(balanceType == 1) {
            String completedV = dfs(v, "", "", 0, "");
            String completedU = "";
            for(int i = 1; i < u.length() - 1; i++) {
                completedU += u.charAt(i) == '(' ? ")" : "(";
            }
            w = v.substring(completedV.length(), v.length());
            completedV = "(" + completedV + ")";
            completedStr += completedV + completedU;
            u = "";
            v = "";
            ptr = 0;
        }
        
        if(ptr == w.length()) {
            return completedStr;
        }
        
        return dfs(w, u + (w.charAt(ptr) + ""), w.substring(ptr + 1, w.length()), ptr + 1, completedStr);
    }
    
    public int getBalanceType(String str) {
        if(str == "")
            return -1;
        
        int openCount = 0;
        int closeCount = 0;
        Stack<Character>stk = new Stack<Character>();
        
        for(int i = 0; i < str.length(); i++) {
            char currChar = str.charAt(i);
            
            if(str.charAt(i) == ')') {
                closeCount++;
                if(!stk.isEmpty()) {
                    if(stk.peek() == '(') {
                        stk.pop();
                        continue;
                    } 
                }
                stk.push(currChar);
            } else {
                openCount++;
                stk.push(currChar);
            }
        }
        
        if (stk.isEmpty()) return 0;
        if (openCount == closeCount) return 1;
        return -1;
    }
    
}