[Algorithm] Programmers :: 괄호 회전하기

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

프로그래머스

string rotation(string& s) // 1칸씩 회전.
{
    string answer = "";
 
    answer += s.substr(1, s.size() - 1);
    answer += s[0];
 
    return answer;
}
 
 
int solution(string s) {
    int answer = 0;
    map<char, char> m;
    vector<char> left = { '[', '(', '{' };
    vector<char> right = { ']', ')', '}' };
    m['['] = ']';
    m['('] = ')';
    m['{'] = '}';
 
    for (int i = 0; i < s.size(); i++)
    {
        stack<char> rs;
        string temp = s;
        bool check = true;
 
        if (temp.back() == left[0] || temp.back() == left[1] || temp.back() == left[2])
        {
            s = rotation(s);
            continue;
        }
 
        while (!temp.empty())
        {
            char curNode = temp.back();
 
            if (curNode == right[0] || curNode == right[1] || curNode == right[2]) //우항이면
            {
                rs.push(curNode);
                temp.pop_back();
            }
            else // 좌항이면
            {
                if (rs.size() == 0) // 우항이 없는데 좌항이 나온다면 X.
                {
                    check = false;
                    break;
                }
                if (rs.top() == m[curNode]) // 우항스택의 탑이랑 맞는 좌항이면
                {
                    rs.pop();
                    temp.pop_back();
                }
                else if(rs.top() != m[curNode])
                {
                    check = false;
                    break;
                }
            }
        }
        
        if (check && rs.size() == 0)
        {
            answer += 1;
        }
        s = rotation(s);
    }
 
    return answer;
}

 

스택의원리를 이용해서 푸는 문제. 처음에 긴가민가하다가 예전에 풀었던 스택문제형태랑 비슷해서 알아챘다.

string자체도 stack구조이기 때문에 그대로 두고, 우항만 보관할 스택하나 선언해서 꺼냈다 넣었다 하면된다.