[ 프로그래머스 ] #76502 : 괄호 회전하기 - JAVA

🔗 괄호 회전하기

문제풀이

• 회전은 단순히 문자열을 2배로 하면 됨 (({[]}) ➡️ ({[]})({[]}))
• 바깥 for문 : 문자열 길이를 n 이라 하면 i=0 부터 n-1 까지 반복 (회전횟수)
• 내부 for문 : j=i 부터 i+n-1 까지 반복

1. 닫히는 괄호(),},]) 가 들어왔을 때, 스택이 비어 있거나 괄호의 쌍이 맞지 않을 때는 올바른 문자열이 아니므로 다음 회전으로 간다.
2. 내부 for문을 모두 수행했을 때 stack에 남아있는 문자가 없다면 올바른 문자열이 맞으므로 answer 횟수를 증가한다.

import java.util.Stack;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(String s) {
        int answer = 0;

        Map<Character,Character>map=new HashMap<>(); // 괄호 
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        int length=s.length(); // 문자열 길이
        s+=s; // 회전 필요없이 문자열 2배로

        A:for(int i=0;i<length;i++){
            ArrayDeque<Character> stack=new ArrayDeque<>();
            for(int j=i;j<length+i;j++){
                char c=s.charAt(j);

                // 열린 괄호라면
                if(!map.containsKey(c)){
                    stack.push(c);
                }else{ // 닫힌 괄호라면
                    // stack 이 비어있거나 짝이 맞지 않다면
                    if(stack.isEmpty()|| !stack.pop().equals(map.get(c))){
                        continue A;
                    }
                }

            }

            if(stack.isEmpty()){
                    answer++;
            }

        }
        return answer;

    }

}

❓ Stack 대신 ArrayDeque를 사용한 이유
Stack은 내부적으로 Vector를 상속받아 구현되어 있고 Vector는 모든 메서드가 synchronized 되어 있어, 동기화 비용이 발생해 속도가 느리다.
하지만, ArrayDeque는 동기화를 지원하지 않아 상대적으로 빠르고 코딩테스트에서는 동기화를 지원하지 않기 때문에 ArrayDeque가 훨씬 빠르다.