[프로그래머스] 60058 괄호변환(2020 카카오 블라인드)

1. 문제

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

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

2. 접근방법

문제가 참 불친절한데 친절한 이상한 문제다.

 

괄호를 이쁘게 다시 만들어 내는 것이 목표인 문제인데,

이쁘게 만들어 내는 방법을

왜 이렇게 해야하는지는 안알려줬지만 그냥 시키는 대로 만들어면 만들어진다? 같은 느낌이다.

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

시키는 대로가 이것이고

심지어 재귀로 만들어야 한다는 것까지 알려준다..

그래서 문제가 요구하는데로 딱히 이해할 것 없이

시키는 데로만 구현하면 된다.

 

참고)

2번 과정에서

균형잡힌 괄호 문자열 u,v로 분리하는데

u는 더 이상 균형잡힌 문자열로 분리할 수 없어야 한다고 한다.

 

이 말인 즉슨

))()(( ))(( () 이렇게 생긴 괄호가 있을 때

맨앞에서 봤을때 가장 먼저 찾아지는 균형 잡힌 문자열 ))()(( 을

찾고 나서 +a 로 더 추가 하려면

))()(( ))((과 같이 또다른 균형잡힌 문자열이 추가 되어야만 한다.

 

그러면 u는 두개의 균형잡힌 문자열로 분리가 가능해지므로 조건에 위반이 된다.

그러므로 u는 가장 먼저 찾아지는 균형잡힌 문자열만 가능한 것을 알 수 있다.

3. 자바 코드

public class P60058괄호변환 {

	
	 public String solution(String p) {
		String answer = "";
		answer = recur(p);
		return answer;
	}
	
	 String recur(String s) {
		if (s.length() == 0)
			return "";
		int left = 0;
		int right = 0;
		String u = "";
		String v = "";
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(')
				left++;
			else
				right++;
			if (left == right) {
				u = s.substring(0, i + 1);
				v = i + 1 < s.length() ? s.substring(i + 1) : "";
				break;
			}
		}
		if (goodString(u))
			return u + recur(v);
		else {
			String empty = "(";
			empty += recur(v);
			empty += ")";
			for (int i = 1; i < u.length() - 1; i++)
				empty += u.charAt(i) == '(' ? ')' : '(';
			return empty;
		}
	}

	 boolean goodString(String s) {
		int left = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(')
				left++;
			else {
				if (--left < 0)
					return false;
			}
		}
		return true;
	}
}

4. 마치며

재귀 구현 능력을 보려 한 것 같은데 이렇게 까지 다 알려주면 흠..