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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60058

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

1. 주의할 점

- 문제에 적힌 대로만 구현한다

- 빈 문자열 처리를 알맞게 한다

 

2. 구현

- DFS() 함수에서 다음과 같은 작업을 순차적으로 한다

- 넘겨 받은 파라미터가 빈 문자열이면 그대로 반환한다

- 넘겨 받은 파라미터를 균형잡힌 괄호 문자열 U와 나머지 부분인 V로 나눈다

- isComplete 함수를 통해 U가 올바른 괄호 문자열인지 확인한다

- 올바른 괄호 문자열이라면 U+DFS(V)를 반환한다

- 올바른 괄호 문자열이 아니라면 "("+DFS(V)+")" 뒤에 U의 양끝 문자를 빼고 전부 토글시킨 문자열을 추가해서 반환한다

 

import java.util.*;
import java.io.*;

class Solution {
    
    static boolean isComplete(String str){
        Stack<Character> s = new Stack<>();
        int len = str.length();
        
        for(int i=0;i<len;i++){
            char c = str.charAt(i);
            if(c=='(') s.add(c);
            else{
                if(s.isEmpty()) return false;
                else s.pop();
            }
        }
        return s.isEmpty();
    }
    
    static String dfs(String str){
        int cnt=0,idx=0,len = str.length();
        String result = "";
        //1
        if(str.equals("")) return str;
        while(idx<len){
            char c = str.charAt(idx++);
            if(c=='(') cnt++;
            else cnt--;
            if(cnt==0) break;
        }
        //2
        String u = str.substring(0,idx);
        String v = str.substring(idx,len);
        
        //3
        if(isComplete(u)){
            result = u + dfs(v);
        }
        else{
            result = "("+dfs(v)+")";
            int ulen = u.length();
            for(int i=1;i<ulen-1;i++){
                char c = u.charAt(i);
                if(c=='(') result+=')';
                else result+='(';
            }
        }
        return result;
    }
    
    public String solution(String p) {
        String answer = dfs(p);
        return answer;
    }
}