개요

괄호회전하기

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

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

접근 방식

1. 소괄호 갯수, 중괄호 갯수, 대괄호 갯수를 선언해주고 갯수를 +-해주면서 구현했더니 틀렸다..

2. 위 문제를 고민하다 찾은 반례는 ({)}이다.
   이 괄호는 올바르지 않지만, 갯수 카운팅하면서 구현하면 맞다고 나온다!

3. 따라서 스택을 이용해 구현했다.

4. 생각해보면 문자열을 굳이 substring이나 char값으로 회전시킬 필요없다!
   offset인덱스를 이용해서 해당 offset인덱스부터 문자열의 끝까지 훑고 지나가고,
   그다음에 0번 인덱스부터 offset 인덱스 까지 훑고 지나가면 회전한 효과를 낸다!

bool RotateAndCheck(const string& inString, int offset)
{
    stack<int> s;

    //회전을 안시켜도 됨. 그냥 offset부터 탐색하면 회전한 효과나옴
    for(int i=offset;i<inString.size();i++)
   	{...}
    for(int i=0;i<offset;i++)
    {...}

전체 코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
bool RotateAndCheck(const string& inString, int offset)
{
    stack<int> s;

    //회전을 안시켜도 됨. 그냥 offset부터 탐색하면 회전한 효과나옴
    for(int i=offset;i<inString.size();i++)
    {
         char elem = inString[i];
        switch(elem)
        {
            case '(':
                s.push(elem);
                break;
            case ')':
                if(s.top() != '(') return false;
                s.pop();
                break;
            case '{':
                s.push(elem);
                break;
            case '}':
                if(s.top() != '{') return false;
                s.pop();
                break;
            case '[':
                s.push(elem);
                break;
            case ']':
                if(s.top() != '[') return false;
                s.pop();
                break;
            default:
                break;
        }
    }
    for(int i=0;i<offset;i++)
    {
        char elem = inString[i];
        switch(elem)
        {
            case '(':
                s.push(elem);
                break;
            case ')':
                if(s.top() != '(') return false;
                s.pop();
                break;
            case '{':
                s.push(elem);
                break;
            case '}':
                if(s.top() != '{') return false;
                s.pop();
                break;
            case '[':
                s.push(elem);
                break;
            case ']':
                if(s.top() != '[') return false;
                s.pop();
                break;
            default:
                break;
        }
    }
    if(s.empty()) return true;
    return false;
}

int solution(string s) {
    int answer = 0;
    for(int i=0;i<s.size();i++)
    {
        if(RotateAndCheck(s,i))
        {
            answer ++;
        }
        
    }

    return answer;
    
}