[알고리즘] 괄호 회전하기

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

프로그래머스

 

평범한 스택문제입니다.

 

괄호하면 바로 스택이 떠오르죠 '['가 top이라면 ]가 들어왔을 때 pop을 하는 등의 여러 응용을 하게됩니다.

 

해당 문제는 기본적인  괄호 stack문제에서 순환 키워드만 들고왔습니다. 단순히 인덱스를 순회하면서 같은 함수를 타게 만들어주면됩니다.

 

더 최적화할 수 있겠지만 빠르게 코딩해보았습니다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

bool check(string& s, int startIdx, int size)
{
    stack<char> stk;
        
    for (int i = 0; i < size; ++i)
    {
        int curIdx = (startIdx + i + size) % size;

        if (stk.empty())
        {
            stk.push(s[curIdx]);
        }
        else
        {
            char top = stk.top();
            if (s[curIdx] == ')' && top == '(')
            {
                stk.pop();
            }
            else if (s[curIdx] == '}' && top == '{')
            {
                stk.pop();
            }
            else if (s[curIdx] == ']' && top == '[')
            {
                stk.pop();
            }
            else
            {
                stk.push(s[curIdx]);
            }
        }
    }

    return stk.size() == 0;
}

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

    int size = s.size();

    for (int i = 0; i < size; ++i)
    {
        if (check(s, i, size))
            ++answer;
    }

    return answer;
}

코드를 읽으면 최적화할만한 부분을 많이 볼 수 있을 것입니다.