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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

코드

package Programmers.Level2;

// 괄호변환
public class ParenthesisChange {

	public static void main(String[] args) {

		String s= "()(())";


		String result = solution(s);

		System.out.println(" result : " + result );

	}

	public static String solution(String p) {

		if ( p.equals("") ) return "";
		
		if ( check(p) ) return p;

		String answer = "";

		int right= 0;
		int left = 0;
		int index = 0 ;

		for ( char c : p.toCharArray() ) {
			index++;

			if(c=='(') left++;
			else if(c==')') right++;

			if ( right==left ) {
				break;
			}
		}

		String u = p.substring(0,index);
		String v = p.substring(index,p.length());
		
		System.out.println("u : " + u +", v : " + v );
		
		if ( check(u) ) {
			answer=u;
			answer+=solution(v);
		}else {
			answer+="(";
			answer+=solution(v);
			answer+=")";
			
			u = u.substring(1,u.length()-1);

			for( char c : u.toCharArray() ) {
				if(c==')') {
					answer+="(";
				}else if(c=='(')
					answer+=")";
			}
		}
		return answer;
	}

	// 올바른지 아닌지 check 
	private static boolean check(String p) {

		int cnt = 0 ;

		for ( char c : p.toCharArray() ) {
			if(c=='(') cnt++;
			else if(c==')') cnt--;

			if(cnt < 0 ) return false;
		}

		return true;
	}
}

제출 결과

나의풀이

문제를 이해하는데 시간이 오래 걸렸다..

 

결국 균형잡힌 문자열이 주어지면, 문제에 주어진 규칙에 맞추어서 올바른 문자열을 만드라는 소리이다.

 

그래서 문제를 코드로 풀어내면 되는것인데..

 

이게 말처럼 쉽지는 않았다..

 

작성한 코드를 풀이하면

 

1. 빈 문자열인 경우에는 빈 문자열을 반환한다.

 

2. 문자열이 올바른 문자열인지 check하여, 그렇다면 입력 문자열을 그대로 반환한다.

 

* 올바른 문자열은, "("인 경우에는 cnt를 ++, ")"인 경우에는 cnt를--하면서 음수가 되는 경우에는 false를 그렇지 않다면 true를 리턴하게 하였다.

문제에서 "균형잡힌 괄호 문자열"이 매개변수로 주어진다고 했으므로 이 조건은 항상 성립한다.

 

3. 문자열을 loop처리하며, "("인 경우에는 left를 ++, ")"인 경우에는 right를 ++해서 "("와 ")"가 같아지는 시점에 break해주었다.

최초 left == right의 조건에 break를 하는 이유는, u를 더이상 균형잡힌 괄호 문자열로 분리할 수 없어야하기 때문이다.

 

4. break된 index를 기준으로 문자열을 substring하여 u,v를 구해준다.

 

5. u가 올바른 문자열인지 check하여, 올바르다면 올바른 문자열 + v를 재귀한 결과를 더한다.

 

6. u가 올바르지 않다면 문제의 규칙에따라 새로운 문자열을 만든다.

 

음.. 그냥 글로 된 문제를 코드로 풀어보는 것뿐이지만 생각한것만큼 쉽게 구현되지않았다..

 

이런 성격의 문제를 금방 구현해내는것에 익숙해진다면 점점 더 잘해질 것 같다..