[월간 코드 챌린지 시즌2] 괄호 회전하기

[월간 코드 챌린지 시즌2] 괄호 회전하기

🙋‍♂️ 들어가며

이번 문제는 각 idx별로 N길이만큼 보는 stack 응용 문제다

해당 코드는 stack 구현으로 작성되어 라이브러리 X 다

먼저 생각해볼 조건은 다음과 같다.

1. 여는 괄호일 때 -> 무조건 추가

2. 닫는 괄호일 때
  2-1. 스택이 빈칸이라면 불가능 -> 반례 )(, ][, }{, ]( 등등
  2-2. 짝을 지어서 (), {}, [] 인 것만 제거하고 나머지는 불가능으로 간주.
  
3. 최종 검사 -> 스택이 빈칸 && flag == true 일때 cnt++

✅ 코드

class Solution {
    public int solution(String s) {
        int answer = 0;
        int N = s.length();
        
        
        // 1. 각 회전마다 stack 내부의 괄호를 제거할 수 있나 확인
        for (int i = 0; i < N; i++) {
            boolean flag = true;
            char[] stack = new char[N];
            int top = -1;
            
            // 2. 회전
            for (int j = 0; j < N; j++) {
                // 2-1. 회전하는 idx
                int idx = (i+j) % N;
                char ch = s.charAt(idx);
                
                // 여는 괄호면 stack에 추가
                if (ch == '(' || ch == '{' || ch == '[') {
                    stack[++top] = ch;
                }
                // 닫는 괄호일때
                else if (ch == ')' || ch == '}' || ch == ']') {
                    // 스택이 현재 빈칸이라면 볼필요도 없다
                    if (top == -1) {
                        flag = false;
                        break;
                    }
                    // 매칭되면 stack 칸 줄이자
                    char peek = stack[top];
                    if (peek == '(' && ch == ')') {
                        top--;
                    }
                    else if (peek == '{' && ch == '}') {
                        top--;
                    }
                    else if (peek == '[' && ch == ']') {
                        top--;
                    }
                    else {
                        flag = false;
                        break;
                    }
                }
            }
            // 스택이 빈칸이고 true일때 answer++
            if (top == -1 && flag) answer++;
        }
        
        return answer;
    }
}