[프로그래머스] 괄호 회전하기 (C++)

풀이

주어진 문자열을 왼쪽으로 X칸만큼 회전시켰을 때, 주어진 문자열이 올바른 괄호 문자열이면 개수를 카운트하는 문제다. 쪼개서 문제를 해결해보자.

 

올바른 괄호 문자열인지 판단하는 방법은 stack 자료구조를 이용하면 쉽게 판별할 수 있다.

여는 괄호 '(', '{', '[' 가 들어오면 stack에 push

닫는 괄호 ')', '}', ']' 가 나오면 아래의 조건을 체크해야 한다.

1. 스택이 비어있는데 닫는 괄호가 나오면 이 문자열은 올바른 괄호 문자열이 아니다.

2. 스택이 비어있지 않다면 가장 윗단의 여는 괄호와 닫는 괄호를 비교해서 맞다면 pop 아니라면 올바른 괄호 문자열이 아니다.

 

왼쪽으로 x칸만큼 회전시키는 방법은 deque 자료구조를 이용하면 쉽게 구현할 수 있다.

deque는 양쪽에 삽입 및 삭제가 가능하기 때문이다.

따라서 해당 x칸만큼 반복문을 돌려서 앞에서 빼고, 뒤에 삽입하면 된다.

 

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

int solution(string s) {
    int answer = 0;
    int loop = s.size();
    bool isValid;
    deque<char> dq(s.begin(), s.end());
    while(loop--) {
        dq.push_back(dq.front());
        dq.pop_front();
        stack<char> st;
        isValid = true;
        for(int i = 0; i < dq.size(); i++) {
            if(dq[i] == '[' || dq[i] == '(' || dq[i] == '{') st.push(dq[i]);
            else {
                if(st.empty()) {
                    isValid = false;
                    break;
                }
                else if(dq[i] == ']' && st.top() == '[') st.pop();
                else if(dq[i] == ')' && st.top() == '(') st.pop();
                else if(dq[i] == '}' && st.top() == '{') st.pop();
            }
        }
        
        if(!st.empty()) isValid = false;
        if(isValid) answer++;
    }
    
    
    return answer;
}