[프로그래머스/c++] Lv2 괄호 회전하기

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

프로그래머스

괄호를 회전하기 위해 deque를 사용하였다. 굳이 사용 안해도 되지만..나는 그렇게 풀었다. 

 

1. 완전한 괄호인지 판단하기 위해 isValid 함수와 stack을 사용하였다. 

2. (, [, { 가 나오게 되면 올바른 괄호의 조건이 되기 때문에 stack에 넣는다. 

3. 만약 그렇지 않으면 

 3-1. 스택이 비어있을 때 ),], } 를 만나면 올바르지 않은 괄호이기 때문에 return false를 해준다. 

 3-2. 스택이 비어있지는 않지만, 올바르지 않은 괄호일 때도 return false를 해준다. 

 3-3. 짝이 맞는 괄호가 있을 때, 스택 top을 하나씩 삭제해준다. 

4. 올바른 괄호가 되면 return stk.empty()를 해준다. -> stack이 비어있어야지만 올바른 문자열이기 때문 

5. 회전하는 괄호를 만들어주기 위해 deque를 사용해준다. 

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

bool isValid(deque<char>& dq) {
    stack<char> stk;

    for (char c : dq) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        }
        else {
            if (stk.empty())
                return false;
            char top = stk.top();
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')){
                return false;
            }
            stk.pop();
        }
    }
    return stk.empty();
}

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

    deque<char> dq(s.begin(), s.end());

    for (int i = 0; i < s.size(); i++) {
        if (isValid(dq))
            answer++;
        char front = dq.front();
        dq.pop_front();
        dq.push_back(front);
    }

    return answer;
}