괄호 회전하기/C++

프로그래머스

올바른 괄호 문자열이 되기 위해서는

1. 문자열이 닫는 부호로 시작해서는 안된다.

2. 여는 부호 다음에는 여는 부호 또는 해당 부호를 닫는 부호가 나와야한다.

3. 위 조건에 맞춰 짝이 맞춰진 후 남는 부호가 없어야한다.

 

풀이 방법

이번에는 괄호끼리 매칭시켜 짝이 맞는 괄호는 삭제하기위해 스택을 사용하였다.

 

1. char형 스택 bracket을 선언

2. 올바른 괄호인지 판별하기 위한 bool형 flag를 선언

3. bracket이 비어있을 때 s[j]가 닫는 부호라면 올바른 괄호 문자열이 아니므로 flag에 false를 대입 하고 break한다.

4-1. bracket이 비어있지 않을 때 s[j]가 여는 부호라면 bracket에 넣는다.

4-2. bracket.top()이 각각 '(', '{', '['일 때 s[j]가 ')', '}', ']', 즉 괄호가 올바르게 짝지어지면 bracket.pop()을 한다.

4-3. 위 두 조건에 부합하지 않는다면 flag에 false를 대입하고 break한다.

5. 위 조건문들이 끝난 후 bracket이 비어 있고 flag가 true라면 answer++

6. 문자열을 한 칸씩 회전시켜준다.

7. 반복문이 끝나면 answer 리턴

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for(int i = 0; i < s.length(); i++) {
        stack<char> bracket;
        bool flag = true;
        for(int j = 0; j < s.length(); j++) {
            if(bracket.empty()){
                if(s[j] == ')' || s[j] == '}' || s[j] == ']') {
                    flag = false;
                    break;
                }
                else bracket.push(s[j]);
            } else {
                if(s[j] == '(' || s[j] == '{' || s[j] == '[')
                    bracket.push(s[j]);
                else if(bracket.top() == '(' && s[j] == ')' || 
                        bracket.top() == '{' && s[j] == '}' || 
                        bracket.top() == '[' && s[j] == ']') bracket.pop();
                else {
                    flag = false;
                    break;
                }
            }
        } 
        if(bracket.empty() && flag) answer++;

        char tmp = s[0];
        s.erase(s.begin());
        s += tmp;
    }
    
    return answer;
}