2020 KAKAO BLIND RECRUITMENT - 괄호 변환

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

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

---

import java.util.Stack;

public class Solution {

	public static String solution(String p) {
		String answer = "";
		
		
		// 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
		if(p.equals("")) return answer;
		else {
			String u="", v="";
			int left = 0;
			int right = 0;
			
			// 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리합니다.
			for(int i=0; i<p.length(); i++) {
				
				if(p.charAt(i) == '(') left ++ ;
				else if(p.charAt(i) == ')') right ++;
				
				if(left == right) { // u 는 균형잡힌 문자열
					u = p.substring(0, left+right);
					v = p.substring(left+right, p.length());
					break;
				}
			}
			
			// System.out.println("u : " + u + "         v :" + v);
			if(isRight(u)) { // u가 올바른 문자열이라면
				answer = u + solution(v);
			} else { // 아니면
				answer += "("; // 빈 문자열에 첫번째 문자로 '('를 붙입니다.
				answer += solution(v) + ")"; // v 에 대해 1단계부터 재귀적으로 수행한 결과를 이어 붙인다. + ) 를 붙인다.
				// u의 첫 번째와 마지막 문자를 제거하고, 
				u = u.substring(1, u.length()-1);
				// 나머지 문자열의 괄호 방향을 뒤집어서 다시 뒤에 붙인다.
				String U = "";
				for(int j=0; j<u.length(); j++) {
					if(u.charAt(j) == '(') U += ")";
					else U += "(";
				}
				answer += U;
			}
			
		}
		
		return answer;
	}
	
	public static boolean isRight(String st) {
		Stack<Character> stack = new Stack();
		
		for(int i=0; i<st.length(); i++) {
			char c = st.charAt(i);
			if(c == '(') {
				stack.push(c);
			} else { // c == ')'
				if(stack.isEmpty() || stack.peek() != '(') return false;
				else stack.pop();
			}
		}
		
		if(stack.size() == 0) return true;
		else return false;
	}
}