[JAVA] 프로그래머스 - 괄호 변환

문제내용

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

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

카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의

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

'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.

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

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

 

---

문제 접근 방법

개인적으로 2번 부분에 문자열을 분리하는 부분이 이해가 안가서 더 오래 걸렸던 문제이다.

이해가 안갔던 이유는 분리하는 기준이 뭔지 감이 잡히지 않았기 때문에 어떤 기준을 잡고 분리해야하는지 고민을 좀했다. 그리고 고민한 결과

분리된 문자열 u는 무조건 '균형잡힌 문자열'로 더이상 분리 할 수 없다는 조건이 있다.

이 말은 w문자열에 대해 처음부터 끝까지 탐색해가며 옳바른 문자열이든 아니든 무조건 균형잡힌 문자열이 첫번째로 등장하는 순간 분리가 된다는 말이다. 즉, 괄호의 개수가 처음으로 같아지는 순간이다.

내 기준에는 문제에서 저부분만 이해된다면 다른 부분에서 모두 이해가 될꺼라 생각하기 때문에 바로 풀이에 대한 접근 방법으로 넘어가 보겠다.

 

풀이에는 총 3가지 메소드를 필요로 한다.

1. 문자열 분리(메소드 separation)
   가장 먼저 해야 하는것은 현재 갖고 있는 문자열을 u,v로 분리해야 한다. 분리하는 방법은 위에서 말했듯이 괄호의 개수가 처음으로 같아지는 순간을 기준으로 하여 u,v로 분리하면 된다. 또한 u,v의 문자열을 가변성을 갖고 있기때문에 StringBuilder로 선언하는것이 좋다고 생가한다.
2. 문자열 검사(메소드 checkStringU)
   문제에서 문자열 검사에 관한 부분이 필요하다. 여기서 말하는 문자열 검사란, 분리한 문자열 u가 옳바른 문자열인지 아닌지에 따라 알고리즘의 작업이 달라지기 때문에 분리 후 바로 문자열 검사를 해줘야한다.
   그리고 문자열 검사를 하는 방법은 여러가지가 있겠지만 나는 Stack과 배열을 이용했다. 이에 대한 알고리즘은 전에 프로그래머스에서 "짝지어 제거하기" 의 문제와 유사한 알고리즘이다.
   
   Stack에 있는 문자와 배열에 있는 문자를 비교해가며 옳바른 짝일땐 Stack의 문자를 pop하는 방식으로 했고, 이때 결과가 Stack이 비어있다면 옳바른 문자열로 판단하는 코드를 작성했다.
   (Stack에 있는 문자는 이전 문자, 배열에 있는 문자는 현재 문자)
   1. u가 옳바른 문자열 일때
      단순하게 문제에서 요구한 대로 u 문자열에 v에대한 재귀 수행후 결과값을 붙여주면된다.
      v에 대한 재귀는 separtion(v.toString()); 이 된다.
   2. u가 옳바른 문자열이 아닐때
      이부분도 마찬가지로 문제에서 요구한 대로 수행하면 된다. 즉, 새로운 문자열을 str이라 할때
      str = "(" + "v에 대한 재귀" + ")" + "u에 대한 문자열 조작" 이된다.
      이때 "u에 대한 문자열 조작" 이란 문제에서 4-4 부분에 해당한다.
3. u에 대한 문자열 조작(메소드 reverse)
   u가 옳바른 문자열이 아닐때 실행되는 메소드이며 앞뒤 문자 제거 후 남은 괄호는 각각 뒤집어서 반환해주는 메소드이다.

위의 3가지 메소드를 이용해 문제를 풀어낼 수 있다.

코드를 보면 알겠지만 생각보다 간다하게 풀리는데 나는 몇시간 동안 고민했었고, 2번 부분을 제대로 풀어내지 못해서 다른 블로그 글들을 참고했다.

 

풀이를 보자

 

---

풀이

import java.util.Stack;

public class Solution {
	public static String solution(String p) {
		String answer = "";
		
		//처음부터 옳바른 문자열일 경우 그대로 반환 후 종료
		if(checkStringU(p)) {
			return answer=p;
		}
		
		//separation 메소드로 문자열 u,v로 분리 후 문자열 만들어서
		//answer에 대입.
		answer = separation(p);
		return answer;
	}
	
	//u,v로 문자열 분리시킨후 answer을 만들어주는 메소드
	public static String separation(String w) {
		if(w.length()==0) { return ""; }//빈문자열은 바로 반환
		//u,v 및 괄호 개수에관한 변수 정의.
		StringBuilder u = new StringBuilder();
		StringBuilder v = new StringBuilder();
		int bracket = 0;
		
		for(int i=0; i<w.length(); i++) {
			//괄호의 방향에 따라 bracket 변수 증감.
			//증감 후 bracket이 0이 되는 순간 i번째에서 균형잡힌 문자열이 되는것.
			//즉, '(' 와 ')'의 개수가 같아지는 순간임.
			if(w.charAt(i)=='(') {bracket++;}
			else {bracket--;}
			
			if(bracket==0) {//i번째에서 최초로 균형잡힌 문자열이 됐을때
				//u,v에 i를 기준으로 문자열 w를 나눠서 넣어줌.
				//문제에 2 번에 관한 부분.
				u.append(w.substring(0,i+1));
				v.append(w.substring(i+1, w.length()));
				
				//문제에서 3,4번에 관한 부분.
				//나눠진 문자열에서 u가 옳바른지 아닌지에 따라 경우가 달라짐.
				if(checkStringU(u.toString())) {//옳바른 경우, 3.번에 관한 부분
					//옳바른 문자열 u에다가 v에 대해 재귀 수행 후 나온 문자열을 붙임.
					u.append(separation(v.toString()));
					/*
					 * i번째에서 문자열 나누고 재귀 수행 후에 더이상 다음 i번째로
					 * 갈필요가 없음. 재귀 수행하고 나온 문자열을 for문 종료시키고
					 * return 해주면됨.
					*/
					break;
				}
				else {//옳바르지 않은 경우, 4번에 관한 부분.
					StringBuilder str = new StringBuilder();
					str.append("(");//4-1
					str.append(separation(v.toString()));//4-2
					str.append(")").append(reverse(u.toString()));//4-3,4-4
					return str.toString();//4-5
				}
			}//if, 2번
		}//for
		
		return u.toString();//3-1;
	}//separtion(String p)
	
	
	//문자열 u에 대한 조작. 4-4를 나타내는 메소드
	public static String reverse(String u) {
		StringBuilder str = new StringBuilder();
		
		//앞뒤문자 제거 후 문자열 뒤집기
		for(int i=1; i<u.length()-1; i++) {
			if(u.charAt(i)==')') {str.append("(");}
			else {str.append(")");}
		}
		return str.toString();
	}
	
	//옳바른 문자열인지 아닌지 체크하는 메소드
	//반환값 true -> 옳바른것, false -> 균형잡힌것
	public static boolean checkStringU(String u) {
		boolean ans = false;
		Stack<Character> st = new Stack<Character>();
		char[] arr = u.toCharArray();
		
		//stack에 있는 문자열-> 전에 있던 문자
		//arr[i] -> 현재 문자
		//전과 현재를 비교 후 옳바른 짝이라면 stack에서 문자 제거.
		for(int i=0; i<arr.length; i++) {
			if(!st.isEmpty() && st.peek()=='(' && arr[i]==')') {
				st.pop();
			}else {
				st.push(arr[i]);
			}
		}
		
		if(st.isEmpty()) {ans = true;}
		
		return ans;
	}
}

---

마치며

코드를 작성하고 나서 보면 이해하지 못할 코드는 없다.. 하지만 이번 문제로 알게된건 재귀에 대해 내가 아직 부족하다고 느끼게 해준 문제이다. 재귀는 아직도 어려운 느낌이라 더해봐야 할것같다ㅠㅠ