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

 

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

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

 

약 23%의 정답률인 문제입니다.

1~4번을 구현하면 되는 쉬운 문제였네요.

 

문제가 한 번에 이해가 되지 않아 직접 손으로 그려가며 풀었습니다.

---

메소드

String solution

주어진 입력값이 올바른 괄호 문자열이라면 그대로 반환합니다.

그렇지 않다면 재귀를 시작합니다.

(check, rec 호출)

 

String rec

주어진 문자열이 빈 문자열이면 빈 문자열을 반환합니다.

s에서 u와 v로 분리합니다. temp와 index를 통해 균형 잡힌 괄호 문자열을 검사했습니다.

 

u가 올바른 괄호 문자열이라면 u + rec(v)를 반환하며 v에 대해 다시 재귀 함수를 호출합니다.

3-1까지 구현 완료.

 

u가 올바른 괄호 문자열이 아니라면 문제에서 주어진 동작을 수행합니다.

그리고 만들어진 문자열을 반환합니다.

 

boolean check

파라미터의 문자열이 올바른 괄호 문자열인지 판별합니다. 

c가 ')'일 때 스택은 비어있지 않아야 합니다.

또, 문자열의 끝까지 갔을 때 스택은 비어있어야 합니다.

import java.util.*;

class Solution {

	public static String solution(String p) {
		if(check(p))
			return p;
		return rec(p);
	}

	public static String rec(String s) {
		if(s.equals(""))
			return "";

		int temp = 0;
		String u = "", v = "";

		for(int i = 0; i < s.length(); i++) {
			char c= s.charAt(i);
			if(c == '(')
				temp ++;
			else
				temp --;
			if(temp == 0 && i != 0) {
				u = s.substring(0, i+1);
				if(i + 1 != s.length())
					v = s.substring(i+1, s.length());
				else
					v = "";
				break;
			}
		}

		if(check(u)) {
			return u + rec(v);
		}
		else {
			StringBuilder sb = new StringBuilder();
			sb.append("(");
			sb.append(rec(v)+")");
			for(int i = 1; i < u.length()-1; i++) {
				char c = u.charAt(i);
				if(c == '(')
					sb.append(")");
				else
					sb.append('(');
			}
			return sb.toString();
		}
	}

	public static boolean check(String p) {
		Stack<Character> st = new Stack<Character>();
		for(int i = 0; i < p.length(); i++) {
			char c = p.charAt(i);
			if(c == '(')
				st.push(c);
			else {
				if(st.isEmpty())
					return false;
				st.pop();
			}
		}

		return true;
	}
}