📒활용개념

1. stack과 queue를 활용하여 문제풀이
   -stack의 후입 선출과 queue의 선입 선출을 활용한 문제풀이

📌문제설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

📌구현

#include <string>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

//queue에 담겨있는 괄호가 올바른 괄호 문자열인지 확인하는 함수
bool check (queue<char> q){
	//stack의 후입선출을 통한 적절성 확인
    stack<char> st;
    st.push(q.front());
    q.pop();
    while(!q.empty()){
        char ch = q.front();
        q.pop();
        //닫는 괄호가 나왔을 때 적절성 확인
        if((ch==']'||ch=='}'||ch==')')&&!st.empty()){
            char ch2 = st.top();
            if(ch==']'){
                if(ch2=='['){
                    st.pop();
                }
                else{
                    return false;
                }
            }
            else if(ch=='}'){
                if(ch2=='{'){
                    st.pop();
                }
                else{
                    return false;
                }
            }
            else if(ch==')'){
                if(ch2=='('){
                    st.pop();
                }
                else{
                    return false;
                }
            }
            else{
                return false;
            }
        }
        //여는 괄호는 모두 stack에 삽입
        else{
            st.push(ch);
        }
        
    }
    
    //마지막에 stack이 비어있지 않다면 올바른 괄호가 아님
    if(!st.empty()){
        return false;
    }
    return true;
}

int solution(string s) {
    int answer = 0;
    //queue의 선입선출을 활용해 가능 모든 괄호의 경우의 수를 만든다.
    queue<char> bracket;
    
    for(int i=0; i<s.size(); i++){
        bracket.push(s[i]);
    }
    //가능한 괄호인 경우 answer+1
    if(check(bracket)){
        answer++;
    }
    //괄호를 하나씩 움직이며 가능한지 여부 판단.
    for(int i=1; i<s.size(); i++){
        char tmp = bracket.front();
        bracket.pop();
        bracket.push(tmp);
        if(check(bracket)){
            answer++;
        }
    }
    
    return answer;
}

📌주의점

• 처음에는 어떻게 모든 괄호의 경우의 수를 확인할지 고민했다. 하지만 queue의 선입선출 특징을 활용하면 앞의 괄호를 먼저 빼고 뒤로 다시 넣으면 된다고 생각했다.
• 괄호가 올바른 괄호인지 확인하는 것은 그 전부터 stack을 활용하여 많이 해봤기 때문에 쉽게 할 수 있었다.