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

2020 KAKAO BLIND RECRUITMENT

---

괄호 변환

---

지문 요약

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. 생성된 문자열을 반환합니다.

 

문제 해석만 완료된다면 수월하게 풀 수 있지만, 애석하게도 문제 해석이 까다롭다. 다만 이런 형태의 괄호 문제를 많이 풀어봤다면, 용어만 조금 익숙해진다면 그래도 충분히 해석 가능한 문제라고 생각한다.

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.

이 부분을 이해하고, 위의 문제를 천천히 읽어본다면, 그 이후로는 지문에 따라 그대로 구현하기만 하면 되는 문제이다.

 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

f (p.isEmpty()) { // 1번
	return "";
}

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

 

private static String[] split(String p) {
		int open = 0;
		int close = 0;
		if (p.charAt(0) == '(') {
			open++;
		} else {
			close++;
		}
		int splitIndex = 1;
		for (int i = 1; i < p.length(); i++) {
			if (p.charAt(i) == '(') {
				open++;
			} else {
				close++;
			}
			if (open == close) {
				splitIndex = i;
				break;
			}
		}
		return new String[] { p.substring(0, splitIndex + 1), p.substring(splitIndex + 1) };
	}

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

		if (balanced(u)) {
			return u + parse(v);
		}

 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

	private static boolean balanced(String u) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < u.length(); i++) {
			if (u.charAt(i) == '(') {
				stack.add(u.charAt(i));
			} else {
				if (!stack.isEmpty()) {
					stack.pop();
				} else {
					return false;
				}
			}
		}
		return true;
	}

4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

4-3. ')'를 다시 붙입니다.

4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 4-5. 생성된 문자열을 반환합니다.

	private static String reverse(String u) {
		StringBuffer sb = new StringBuffer();
		for (int i = 1; i < u.length() - 1; i++) {
			if (u.charAt(i) == '(') {
				sb.append(")");
			} else {
				sb.append("(");
			}
		}
		return sb.toString();
	}
    
u = reverse(u);
return "(" + parse(v) + ")" + u;

코드 전문

import java.util.*;

class Solution {
  public static void main(String[] args) {
		String p = "()))((()";
		System.out.println(solution(p));
	}

	public static String solution(String p) {
		return parse(p);
	}

	private static String parse(String p) {
		if (p.isEmpty()) { // 1번
			return "";
		}
		String[] strs = split(p);
		String u = strs[0];
		String v = strs[1];

		if (balanced(u)) {
			return u + parse(v);
		}

		u = reverse(u);
		return "(" + parse(v) + ")" + u;
	}

	private static String reverse(String u) {
		StringBuffer sb = new StringBuffer();
		for (int i = 1; i < u.length() - 1; i++) {
			if (u.charAt(i) == '(') {
				sb.append(")");
			} else {
				sb.append("(");
			}
		}
		return sb.toString();
	}

	private static boolean balanced(String u) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < u.length(); i++) {
			if (u.charAt(i) == '(') {
				stack.add(u.charAt(i));
			} else {
				if (!stack.isEmpty()) {
					stack.pop();
				} else {
					return false;
				}
			}
		}
		return true;
	}

	private static String[] split(String p) {
		int open = 0;
		int close = 0;
		if (p.charAt(0) == '(') {
			open++;
		} else {
			close++;
		}
		int splitIndex = 1;
		for (int i = 1; i < p.length(); i++) {
			if (p.charAt(i) == '(') {
				open++;
			} else {
				close++;
			}
			if (open == close) {
				splitIndex = i;
				break;
			}
		}
		return new String[] { p.substring(0, splitIndex + 1), p.substring(splitIndex + 1) };
	}
}