[Java] 2020 KAKAO BLIND RECRUITMENT - 괄호 변환 (Lv2)

그동안 여러번 도전했다가 못풀고 그냥 넘겼던 괄호 변환을 다시 도전해서 해결했다 🔥

 

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

프로그래머스

 

 

✔ 입출력 예시

괄호 변환 입출력 예시

 

 

💡 포인트

1️⃣ 문제에 나와있는 문자열 변환 과정을 천천히 따라가며 구현하는 것이 가장 좋은 문제 포인트

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

 

 

✔ 소스코드

import java.util.Stack;

public class Solution { // 괄호 변환

	public static void main(String[] args) {
		String p = "(()())()";
//		String p = ")(";
//		String p = "()))((()";

		System.out.println(solution(p));
	}

	private static String solution(String p) {
		String answer = "";
		
		// 1단계
		if(p.length() == 0) {
			return answer;
		}
		
		// 2단계
		StringBuilder u = new StringBuilder();
		StringBuilder v = new StringBuilder();
		int bracket = 0;
		for(int i=0; i<p.length(); i++) {
			u.append(p.charAt(i));
			if(p.charAt(i) == '(') bracket++;
			else bracket--;
			
			if(bracket == 0) {  // u가 균형잡힌 문자열이라면
				v.append(p.substring(i+1));
				break;
			}
		}
		
		// 3단계 & 4단계
		if(isBalance(u.toString())) {  // u가 올바른 괄호 문자열이라면
			answer += u.toString();
			answer += solution(v.toString());
		} else {
			StringBuilder sb = new StringBuilder();
			sb.append("(");
			sb.append(solution(v.toString()));
			sb.append(")");
			for(int i=1; i< u.length()-1; i++) {
				if(u.charAt(i) == '(') {
					sb.append(')');
				} else {
					sb.append('(');
				}
			}
			answer = sb.toString();
		}
		
		return answer;
	}

    // 올바른 괄호 문자열 판별 함수
	private static boolean isBalance(String u) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < u.length(); i++) {
			char b = u.charAt(i);
			if(stack.isEmpty() && b==')') {  // 첫 괄호가 닫는 괄호라면 올바른 괄호 x
				return false;
			}
			if(!stack.isEmpty() && stack.peek() == '(' && b == ')') {  // 괄호가 짝을 이룬다면 stack의 top을 없애기
				stack.pop();
			} else {
				stack.push(b);
			}
		}

		if(!stack.isEmpty()) {  // 스택이 비어있지 않다면 올바른 괄호 x
			return false;
		}
		return true;
	}
}

     1️⃣ 균형잡힌 괄호 문자열인지는 괄호의 열린 괄호와 닫힌 괄호의 개수만 맞으면 되므로 굳이 판별 함수를 따로 생성

           하지 않고 bracket이라는 정수 변수를 이용하여 판별함

     2️⃣ 올바른 괄호 문자열인지는 개수뿐만 아니라 열린 괄호 + 닫는 괄호 순으로 쌍이 맞아야 하므로 Stack을 이용하여

           풀이 (쌍이 맞으면 stack에서 pop(), 쌍이 맞지 않으면 stack에 push()하여, 마지막에 stack()이 비어있지 않으면

           올바른 괄호 ❌)

 

 

❗ 결과

    👉 테스트 통과

 

천천히 생각을 정리해보며 도전해보니 너무 쉽게 통과했던 문제였다... 생각보다 너무 쉽게 풀려서 허무...

문제가 해결되지 않을때는 잠시 다른 문제를 풀었다가 후에 다시 도전해보는 것도 좋은 것 같다 🔥