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

🖊️ 문제

괄호 회전하기  

 

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

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

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

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

 

🖥️ 코드

#include <string>
#include <stack>

using namespace std;

bool isValid(string s)
{
    stack<char> st;

    for (int j = 0; j < s.size(); j++)
    {
        if (s[j] == '(' || s[j] == '{' || s[j] == '[')
            st.push(s[j]);
        else
        {
            if (st.empty()) return false;
            if (s[j] == ')' && st.top() == '(') st.pop();
            else if (s[j] == '}' && st.top() == '{') st.pop();
            else if (s[j] == ']' && st.top() == '[') st.pop();
        }
    }
    return st.empty() ? true : false;
}


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

    for (int i = 0; i < s.size(); i++)
    {
        s += s.front();
        s.erase(s.begin());

        if (isValid(s)) answer++;
    }

    return answer;
}

 

🤔 나의 생각

시작 괄호 '(', '{', '['는 stack에 push한다. 반대로 stack의 top에 대응되는 ')' '}' ']'를 만나면 stack에서 pop하면 된다. 

 

다만 몇 가지 경우의 수를 생각해야 한다. 다음과 같은 괄호 문자열 ")()("는 '('괄호 없이 ')'이 등장하므로 올바른 괄호가 아니다. 또한 반복문을 다 돌아도 stack에 무언가 남아있다면 짝수가 맞지 않는 경우이다.

결과적으로 반복문을 다 돌았을 때 만약 stack이 비었다면 짝수와 방향도 알맞은 올바른 괄호 문자열이 된다.

 

올바른 괄호인지 검사하는 문제는 stack을 사용하는 대표적인 문제로 자주 소개된다. 그래서 그런지 프로그래머스에도 stack을 이용한 괄호 문제가 몇 있다. 프로그래머스 Level 2 올바른 괄호 문제를 풀면 본 문제도 쉽게 풀 수 있을 듯하다!