문제 접근

문제에서 나와있는 조건을 따라 그대로 구현하면 된다.
여기서, u는 더이상 쪼갤 수 없는 '균형잡힌 괄호 문자열' 이라고 나와있다. 이 말은 문자열을 앞에서부터 하나하나 읽으면서 최초로 (와 )의 갯수가 같아지는 지점까지를 u로 잡으라는 것과 같다.
이 부분만 빠르게 캐치한다면, 이후는 문제 나온대로 단순 구현이다.
또한, '올바른 괄호 문자열'인지 판단하기 위해서는 스택을 사용했다.

문제 풀이

import java.util.*;

class Solution {
    public String solution(String p) {
        String answer = find(p);
        return answer;
    }
    
    String find(String s) {
        if (s.length() == 0) return "";
        StringBuilder sb = new StringBuilder();
        int sBracket = 0;
        int eBracket = 0;
        int baseIndex = 0;
        for(int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                sBracket++;
            } else {
                eBracket++;
            }
            
            if (sBracket == eBracket) {
                baseIndex = i;
                break;
            }
        }
        
        String u = s.substring(0, baseIndex+1);
        String v = s.substring(baseIndex+1, s.length());
        if (isCollect(u)) {
            sb.append(u).append(find(v));
        } else {
            sb.append('(').append(find(v)).append(')').append(reverse(u.substring(1,u.length()-1)));
        }
        
        return sb.toString();  
    }
    
    boolean isCollect(String s) {
        Stack<Character> stack = new Stack();
        for(int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.add('(');
            } else {
                if (stack.isEmpty()) return false;
                stack.pop();
            }
        }
        
        if (stack.isEmpty()) return true;
        return false;
    }
    
    String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                sb.append(')');
            } else {
                sb.append('(');
            }
        }
        return sb.toString();
    }
}