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

프로그래머스 / Java / 괄호 변환

문제 링크

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

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

문제 풀이

카카오 코딩 테스트로 나왔던 문제죠.

일반적으로 스택 연습문제로 많이 나오는 괄호 문제와 재귀를 많이 풀어보셨다면 무리 없이 금방 풀 수 있는 문제입니다.

 

이 문제는 요구사항을 그대로 구현하면 되는 문제입니다.

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

• 균형잡힌 괄호 문자열을 판단하는 방법은 괄호 문자열을 반복문을 돌려 ( 가 나올 때 ++, )이 나올 때 --하여 그 값이 0이 되면 균형 잡힌 괄호입니다.

• 올바른 괄호 문자열을 판단하는 방법은 괄호 문자열을 반복문을 돌려 ( 가 나올 때 ++, )이 나올 때 --하여 그 값이 0보다 아래가 되는 경우를 가 존재하거나 끝났을 때 0이 아닌 경우를 제외 한 모든 경우가 균형 잡힌 괄호입니다.

 

 

 

소스 코드

class Solution {
    public String solution(String p) {
        return make(p);
    }
    
    	public String make(String w) {
		if("".equals(w)) return w;
		int top=0;
		String u= "";
		String v= "";
        // 균형잡힌 괄호문자열 테스트    
		for(int i=0;i<w.length();i++) {
			if(w.charAt(i) == '(') top++;
			if(w.charAt(i) == ')') top--;
			if(top == 0) {
				u = w.substring(0,i+1);
				v = w.substring(i+1);
				break;
			}
		}
		if(test(u)) return u+make(v);
		else {
			String p ="";
			p = "("+make(v)+")";
			u = u.substring(1,u.length()-1);
			String temp = "";
			for(int i =0;i<u.length();i++) {
				if(u.charAt(i) == '(') temp+=')';
				if(u.charAt(i) == ')') temp+='(';
			}
			u= temp;
			return p+u;
		}
	}
	// 올바른 괄호문자열 테스트
	public boolean test(String p) {
		int top = 0;
		for(int i=0;i<p.length();i++) {
			if(p.charAt(i) == '(') top++;
			if(p.charAt(i) == ')') top--;
			if(top<0) return false;
		}
		if(top!=0) return false;
		return true;
	}
    
}