[TIL] 프로그래머스) 76502 - 괄호 회전하기

 > 괄호 회전하기 문제의 풀이를 적어보았다.

 

학습 키워드: Java, Stack, StringBuilder

 

76502 - 괄호 회전하기

1) 문제 설명 요약 (원문은 링크 참고):

프로그래머스

 - 요약. (, ), {, }, [, ] 중 무작위의 문자가 담긴 배열 s를 회전시키면서 문자열 내에서 유효한 괄호만 표시되는 경우의 수를 구하는 문제다.

 - 조건: 1 <= s.length() <= 1000

 

2-1) 작성한 코드:

import java.lang.StringBuilder;

class Solution {
    private StringBuilder sb = new StringBuilder();
    private StringBuilder st = new StringBuilder();
    public int solution(String s) {
        if (s.length() % 2 == 1) return 0;
        sb.append(s);
        int end = findFirstClosing(0); // find first closing bracket
        while (end >= 0) { // #loop
            rotate(end); // rotate
            if (tryClose(sb.length() - 1)) end = findFirstClosing(0); // close
            else return 0;
        } // #loop end
        
        return sb.length();
    }
    
    private boolean tryClose(int closing) {
        st.setLength(0);
        st.append(sb.charAt(closing));
        
        while (st.length() > 0) {
            if (--closing < 0) break;
            char cur = sb.charAt(closing);
            if (cur == '.') continue;
            if (isClosing(cur)) st.append(cur);
            else {
                int last = st.length() - 1;
                if (canClose(cur, st.charAt(last))) st.setLength(last);
                else return false;
            }
        }
        
        sb.replace(closing, sb.length(), ".");
        return st.length() == 0;
    }
    
    private void rotate (int endIndex) {
        int newStart = endIndex + 1;
        if (newStart == sb.length()) return;
        String sub = sb.substring (newStart, sb.length());
        sb.setLength(newStart);
        sb.insert(0, sub);
    }
    
    private int findFirstClosing(int start) {
        for (int i = start; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (isClosing(c)) return i;
        }
        return -1;
    }
    
    private boolean canClose (char opening, char closing) {
        if (opening + 1 == closing || opening + 2 == closing) return true;
        else return false;
    }   
    
    private boolean isClosing (char c) {
        if (c == '}' || c == ']' || c == ')') return true;
        return false;
    }
}

 

2-2) 풀이:

 - Stack 문제로 흔히 등장하는 유효한 괄호 모양을 만드는 문제다. 그런데 이전에 풀어봤던 케이스들과 다르게 문자열을 회전 시킬 수 있다는 조건이 붙어있다. 여기서 회전이란, 문자열의 맨 앞이나 맨 뒤의 항목을 반대편으로 보내는 작업을 말한다. 원판에 숫자를 써놓고 회전시킨다고 생각하면 편하다. 이 경우, 처음의 문자열이 유효하지 않더라도 회전 시키다보면 유효한 괄호 문자열을 만들 수 있게 된다.

 - Java의 Stack구조는 대상이 문자(char) 타입인 경우 StringBuilder를 사용하면 유사한 작업을 더 빠른 속도로 진행할 수 있다.

 - 괄호가 유효하기 위해서는 열린 괄호와 대치되는 닫힌 괄호가 있어야 하므로 두 개가 한 쌍이다. 따라서 가장 먼저 길이부터 확인하여 홀수일 때 0을 return 해준다.

 

 - 치환을 시작하는 지점과 방향은 적당하게 선택해준다. 이 스크립트는 가장 처음 등장하는 닫힌 괄호를 맨 뒤로 보내고 맨 뒤에서부터 닫힌 괄호를 쌓은 뒤 열린 괄호를 만날 때 마다 Stack에서 상쇄하는 방식으로 작성했다.

 - 한 번의 tryClose 마다 한 묶음의 괄호(중첩된 괄호)를 '.'으로 치환한 뒤 sb에 넣어주게되고, 이후 남은 문자열 중 가장 먼저 등장하는 닫힌 괄호의 위치를 다음 loop에서 rotate에 넘겨줄 수 있도록 기억해준다. 이 작업을 더 이상 닫힌 괄호가 남지 않을 때 까지 반복해준다.

 

 - 중간에 어딘가에서 걸러져서 false를 return한다면 최종 값으로 0을 return한다. 만일 true를 return하며 종료되었다면 최종적으로 stack에 남는 문자열에는 점으로 치환된 괄호만 남는데, 이 점의 개수가 곧 유효한 괄호를 표시할 수 있는 x값의 경우의 수가 된다. 따라서 sb.length()를 return해주면 문제가 해결된다.

 

2-3) 성능 요약:

 - 메모리: 76.1 MB, 시간: 0.08 ms