[Programmars] 괄호변환

문제

• Programmars 60059
• 문제의 저작권은 Programmars에 있습니다.

접근방식

문제의 순서대로 구현해주었다. ex)문자열 p=”()))((()”일 때

1. 문자열을 앞에서부터 여는 괄호 개수 sCnt와 닫는 괄호 eCnt가 같을때까지 탐색한다.
   이때, 여는 괄호와 닫는 괄호를 관리하는 스택 두개를 사용해서 u에 넣을 문자열이 올바른 괄호인지 체크해주는데 닫는 괄호인 경우 여는 스택 sStack에 값이 있으면 괄호의 짝이 맞으므로 pop()하고 eStack에도 pop()을 해준다.
   그리고 반복문 종료 후 두 스택에 하나라도 괄호가 남아있으면 짝이 맞지 않는 것이므로 u는 올바르지 않은 괄호 문자열이 된다.
   • u: (), v: ))((()
2. u가 올바른 괄호 문자열이므로 v를 1번으로 돌아가 분리
   • u: ))((, v: ()
3. u가 올바른 괄호가 아니므로 새로운 newV에 (를 붙인다 => (
   v를 1번에 넣어 분리한다. => () => 올바른 문자열이므로 다시 돌아감 => (()
   )를 붙인다 => (())
   u의 첫번째와 마지막을 제거한다. => )(
   괄호를 뒤집어 v에 이어붙인다 => (()) + ()
   처음의 u인 () + (())()

import java.util.Stack;

class Solution {
    
    static char start = '(';
	static char end = ')';
	static Stack<Character> sStack, eStack;
    
    public static String solution(String p) {
        return divide(p); //u와 v로 분리
    }

	private static String divide(String p) { //u와 v로 분리
		int i = 0, sCnt = 0, eCnt = 0; //여는&닫는 괄호 개수
		String u = "", v = "", ans = "";
		sStack = new Stack<>();
		eStack = new Stack<>();
		
		if(p.isEmpty()) return "";
		
		while(true) {
			System.out.println(p.charAt(i));
			if(p.charAt(i) == start) {
				sStack.add(p.charAt(i));
				sCnt++;
			}else{ //여는 괄호와 비교
				eStack.add(p.charAt(i));
				eCnt++;
				
				if(!sStack.isEmpty()) {
					sStack.pop();
					eStack.pop();
				}
			}
			i++;
			
			if(sCnt == eCnt) break;
		}
		
		u = p.substring(0, i);
		v = p.substring(i, p.length());
		
		//u가 올바른 괄호인지 체크
		if(sStack.isEmpty() && eStack.isEmpty()) {
			ans = u + divide(v);
		}
		else {
			String newV = "(";
		    newV += divide(v);
			newV += ")";
			
			//첫번째와 마지막 문자 제거 후 나머지 문자열의 괄호방향 뒤집기
			String newU = u.substring(1, u.length()-1);
			for(int j=0; j<newU.length(); j++) {
				if(newU.charAt(j) == start) ans += end;
				else ans += start;
			}
			
			ans = newV + ans;
		}
		return ans;
	}
}