시작

우선 이문제는 문자열에 있는 괄호들을 1칸씩 밀어 움직이면서 괄호가 모두 성립하며, 그 성립되는 것이 몇개인지 찾는 문제다. 그렇다면 한번 어떻게 풀어볼지 생각을 해보자.

1. 스택을 만든다.
2. 우선 비어있으면 넣어 놓는다
3. 만약 },],)일 경우 자신의 모양과 같으면서 열리는 괄호가 top에 있는지 확인한다.
4. 만약 top에 있으면 pop, 아니면 push를 하여 계속 찾아본다.
5. 만약 열리는 괄호일 경우 그냥 push를 한다.

이런식으로 간단하게 알고리즘을 짤 수 있다. 그렇다면 한번 알아보자.

for (int j = i; j < sSize + i; j++) {
            int a = 0;
            if (j < sSize) {
                a = j;
            }
            else {
                a = j - sSize;
            }

우선 먼저 한칸씩 밀어서 확인을 해야되기 때문에 i 부터 size+i를 하여 한칸씩 밀어 확인하는데, 만약 j가 범위를 벗어나면 size를 빼 다시 0번부터 확인 할 수 있게 한다.

switch (s[a])
            {
            case '}':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '{') {
                        q.pop();
                    }
                }
                break;
            case ']':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '[') {
                        q.pop();
                    }
                }
                break;
            case ')':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '(') {
                        q.pop();
                    }
                }
                break;
            default:
                q.push(s[a]);
                break;
            }
        }

그러고 잉제 괄호의 모양을 확인한 후 닫는 괄호일 경우 비어있으면 넣고, top을 봤을때 열리는 경우, pop을 하여 없앤다.

if (q.empty()) {
            answer++;
        }

그런다음 마지막엔 stack에 비어있을경우 그것은 알맞는 괄호이기 때문에 answer에 1을 추가를 한다.

코드

#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    int sSize = s.size();
   
    for (int i = 0; i < sSize; i++) {
        stack<char> q;
        for (int j = i; j < sSize + i; j++) {
            int a = 0;
            if (j < sSize) {
                a = j;
            }
            else {
                a = j - sSize;
            }
            switch (s[a])
            {
            case '}':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '{') {
                        q.pop();
                    }
                }
                break;
            case ']':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '[') {
                        q.pop();
                    }
                }
                break;
            case ')':
                if (q.empty()) {
                    q.push(s[a]);
                }
                else {
                    if (q.top() == '(') {
                        q.pop();
                    }
                }
                break;
            default:
                q.push(s[a]);
                break;
            }
        }
        if (q.empty()) {
            answer++;
        }
    }
    return answer;
}