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

문제 풀이

문제 설명은 해당 링크를 참조하자.

각 단계를 그대로 구현하면 되는 단순한 문제다. 그나마 까다로운 거리가 있다면 올바른 문자열인지를 판단하는 방법일 것이다. 이는 stack을 이용하면 판단할 수 있다.

import java.util.Stack;

class Solution {
    public String solution(String p) {
        // 1단계
        if(p.length() == 0) return "";
        
        // 2단계
        int cutLine = 0;
        int openCount = 0, closeCount = 0;

        do{
            if(p.charAt(cutLine) == '(') openCount++;
            else closeCount++;

            cutLine++;
        }while(openCount != closeCount);
        // '('과 ')'의 개수가 맞게 되는 index를 찾는 과정

        String u = p.substring(0, cutLine);
        String v = p.substring(cutLine);
        
        // u가 올바른 괄호 문자열인지를 판단
        Stack<Character> stack = new Stack<>();
        for(char c: u.toCharArray()){
            // ')'가 들어가려고 하는데 stack 맨 위에 '('가 있는 경우
            if(!stack.empty() && stack.peek() == '(' && c == ')')
                stack.pop();
            else stack.add(c);
        }

        // u가 올바른 괄호 문자열이라면 for문이 끝난후 stack이 비어 있어야 함
        boolean isCorrect = stack.empty();

        // 3단계: 올바른 괄호 문자열일 경우
        if(isCorrect) return u + solution(v);
        
        // 4단계: 올바르지 않은 경우
        String str = "(" + solution(v) + ")";
        
        // 4-1 ~ 4-3
        u = u.substring(1, u.length() - 1);
        
        // 4-4, 4-5
        StringBuilder sb = new StringBuilder();
        for(char c: u.toCharArray())
            sb.append(c == '(' ? ')' : '(');

        return str + sb.toString();
    }
}