[프로그래머스] 괄호 회전하기

문제 설명

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

-s의 길이는 1 이상 1,000 이하입니다.

---

풀이

20분
스택 대신 int형 변수로 괄호 개수를 세는 방식으로 처음에 제출했었는데 마지막 테스트 케이스를 통과하지 못했다. 고민을 해보니

({[}])

이런 올바르지 않은 괄호 문자열을 잘못판단하게 되기 때문이었다.

코드

// 04:40 ~ 04:59

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

int solution(string s) {
    int ans = 0;
    for(int j =0; j < s.length(); ++j){
        vector<char> stack;
        for(int i = 0; i < s.length(); ++i){
            if(s[i] == ')'){
                if(stack.empty()) break;
                if(stack.back() == '(') stack.pop_back();
                else stack.push_back(s[i]);
            }
            else if(s[i] == '}'){
                if(stack.empty()) break;
                if(stack.back() == '{') stack.pop_back();
                else stack.push_back(s[i]);
            }
            else if(s[i] == ']'){
                if(stack.empty()) break;
                if(stack.back() == '[') stack.pop_back();
                else stack.push_back(s[i]);
            }
            else stack.push_back(s[i]);
            
            if(i == s.length() - 1 && stack.empty()) ++ans;
        }
        s = s.substr(1, s.length()) + s[0];
    }
    return ans;
}

틀린 코드

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int ans = 0;
    for(int j =0; j < s.length(); ++j){
        int s_cnt = 0, m_cnt = 0, l_cnt = 0;
        for(int i = 0; i < s.length(); ++i){
            if(s[i] == '(') ++s_cnt;
            else if(s[i] == ')') --s_cnt;
            else if(s[i] == '{') ++m_cnt;
            else if(s[i] == '}') --m_cnt;
            else if(s[i] == '[') ++l_cnt;
            else if(s[i] == ']') --l_cnt;
            
            if(s_cnt < 0 || m_cnt < 0 || l_cnt < 0) break;
        }
        if(s_cnt == 0 && m_cnt == 0 && l_cnt == 0) ++ans;
        
        string temp = s.substr(1, s.length()) + s[0];
        s = temp;
    }
    return ans;
}