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

https://programmers.co.kr/learn/courses/30/lessons/60058?language=java

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

 

문제의 길이는 다소 길었지만 단계별로 구현 내용이 꽤 자세하게 적혀있어서 그대로 스텝을 따라가면 되는 문제였다. 나는 4-4단계에서 문자열을 역순으로 바꿔서 결과값을 리턴했는데 이렇게 하면 12번 테스트케이스부터 틀리게 된다.

다시 한 번 확인해보니 괄호의 방향을 바꾸는 것이었고 '(' 와 ')' 의 방향만 바꿔주면 되었다. 그리고 문제 자체에서 아예 재귀적인 구현을 요구했기 때문에 재귀함수를 기준으로 문제를 해결하는 것이 좋다고 생각된다. 그 외에 나는 올바른 문자열과 균형잡힌 문자열을 체크하기 위한 static 메소드를 하나씩 만들어서 필요할때 마다 호출해서 사용했는데 이게 꽤 편리했다.

---

문제 및 참고사항

---

입출력 예제

---

코드

import java.util.Stack;

class Solution
{
    // 올바른 문자열을 충족하는 가장 마지막 인덱스를 리턴
    public static int isRight(String p)
    {
        Stack<Character> s = new Stack<Character>();
        int index = 0;
        
        if(p.length()==0)
        {
            return -1;
        }
        
        s.push(p.charAt(0));
        
        for(index=1; index<p.length(); index++)
        {
            if(s.isEmpty())
            {
                break;
            }
            if(s.peek()==')')
            {
                if(index==1)
                {
                    return -1;
                }
                else
                {
                    s.pop();
                }
            }
            else
            {
                if(p.charAt(index)==')')
                {
                    return index;
                }
                else
                {
                    s.push(p.charAt(index));
                }
            }
        }
        
        return index;
    }
    // 균형잡힌 문자열을 충족하는 가장 마지막 인덱스를 리턴(만족하지 않으면 -1를 리턴)
    public static int isBalance(String p)
    {
        int index = 0;
        int open = 0;
        int close = 0;
        
        for(index=0; index<p.length(); index++)
        {
            if(p.charAt(index)=='(')
            {
                open++;
            }
            else if(p.charAt(index)==')')
            {
                close++;
            }
            if(open==close)
            {
                break;
            }
        }
        
        return index==p.length()?-1:index;
    }
    public String solution(String w)
    {
        // 1 : 빈 문자열일 경우, 그대로 반환
        if(w.length()==0)
        {
            return "";
        }
        
        // 2 : w를 균형잡힌 문자열 u와 나머지 v로 분리
        String u = w.substring(0, isBalance(w)+1);
        String v = w.substring(isBalance(w)+1, w.length());
        
        // 3 : u가 올바른 문자열이면 결과에 u를 붙이고, v에 대해 1단계부터 수행
        if(isRight(u)!=-1)
        {
            return u + solution(v);
        }
        
        // 4 : 올바른 문자열이 아니라면 아래 단계 수행
        // 4-1 ~ 4-3 : '(' + v에 대해 1단계부터 수행 + ')'
        String answer = "(" + solution(v) + ")";
        
        // 4-4-1 : u의 첫 번째와 마지막 문제 제거
        u = u.substring(1, u.length()-1);
                
        // 4-4-2 : 제거되지 않은 중간 부분의 문자열의 괄호 방향을 뒤집어서 결과에 붙이기
        for(int i=0; i<u.length(); i++)
        {
            if(u.charAt(i)=='(')
            {
                answer += ")";
            }
            else
            {
                answer += "(";
            }
        }
        
        // 4-5 : 결과 반환
        return answer;
    }
}