[ 프로그래머스 ] 괄호 회전하기

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/76502

풀이

---

일반적으로 loop문을 통해 올바르지 못한 괄호를 찾고, erase로 해당 부분을 제거하는 방법을 쓸 수 있으나, 이는 시간 초과가 발생한다. 따라서 괄호를 회전하고 stack을 통해 서로 짝을 이룰 때 제거하는 것을 반복하여 stack이 마지막에 비어있는 경우의 수를 return한다.

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

using namespace std;

int solution(string s) 
{
    int answer = 0;

    for (int idx = 0; idx < s.size(); idx++)
    {
        stack<char> st;

        for (int i = 0; i < s.size(); i++)
        {
            if (st.empty())
            {
                st.push(s[i]);
            }

            else
            {
                if (st.top() == '(' && s[i] == ')')
                {
                    st.pop();
                }

                else if (st.top() == '[' && s[i] == ']')
                {
                    st.pop();
                }

                else if (st.top() == '{' && s[i] == '}')
                {
                    st.pop();
                }

                else
                {
                    st.push(s[i]);
                }
            }
        }

        if (st.empty())
        {
            answer++;
        }

        s.push_back(s[0]);
        s.erase(s.begin());
    }

    return answer;
}