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

🔒문제

프로그래머스 Lv2. 2020 KAKAO BLIND RECRUITMENT 괄호변환

🔑해결

"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return하도록 solution 함수를 작성하는 문제이다.

문제에 주어진 알고리즘을 차례대로 풀면 되는 간단한 문제였다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

🔓코드

class Solution {
    Solution sol;
    public String solution(String p) {
        String answer = "";
        
        sol = new Solution();
        
        // 1.입력이 빈 문자열인 경우, 빈 문자열을 반환
        if (p.compareTo("") == 0)
        	return answer;
        
        // 2.문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리
        String[] uv = uv_divide(p);
        System.out.println(uv[0]);
        System.out.println(uv[1]);
        System.out.println(uv[2]);
        
        
        // 3.문자열 u가 "올바른 괄호 문자열"이라면 문자열 v에 대해 1단계부터 다시 수행
        if (uv[2].compareTo("true") == 0) {
        	answer = uv[0] + sol.solution(uv[1]); // 수행한 결과를 u에 이어 붙인 후 반환
        } else { // 4.문자열 u가 "올바른 문자열"이 아니라면 아래 과정을 수행
        	StringBuilder sb = new StringBuilder();
        	sb.append("("); // 4-1.빈 문자열에 첫 번째 문자로 '('를 붙인다
        	sb.append(sol.solution(uv[1])); // 4-2.문자열 v에 대해 1단계부터 재귀적으로 수행한 문자열을 이어 붙인다
        	sb.append(")"); // 4-3.')'를 다시 붙인다.
        	sb.append(uv_reverse(uv[0])); // 4-4.u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙인다
        	answer = sb.toString();
        }
        
        return answer;
    }
    private String uv_reverse(String u) {
    	String re_u = "";
    	
    	StringBuilder sb = new StringBuilder();
    	for (int i = 1; i < u.length()-1; i++) {
			if (u.charAt(i) == '(') {
				sb.append(')');
			} else {				
				sb.append('(');
			}
		}
    	re_u = sb.toString();
    	
    	return re_u;
    }
    
    private String[] uv_divide(String p) {
    	String[] uv = new String[3];
    	
    	boolean flag = true;
    	
    	int l = 0, r = 0;
    	int t = 0;
    	for (t = 0; t < p.length(); t++) {
    		if ((l != 0 || r != 0) && l == r)
    			break;

    		if (p.charAt(t) == '(') {
				l++;
			} else if (p.charAt(t) == ')') {
				r++;
			}
    		if (l < r) {
    			flag = false;
    		}
		}
    	
    	uv[0] = p.substring(0, t);
    	if (t < p.length()) {
    		uv[1] = p.substring(t);
    	} else {
    		uv[1] = "";
    	}
    	uv[2] = flag + "";
    	
    	return uv;
    }
}