프로그래머스, C++) Lv 2. 괄호 회전하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

 

 

접근법

1. 문자열 길이 2배

2. 슬라이딩 윈도우 개념처럼 l과 r로 접근하여 구간별 체크 => 맞음

3. 여는 괄호, 닫는 괄호의 순서와 카운팅으로 체크하려 했으나 반례가 너무 많음. 

반례: (   [   )   ] 

원래 접근법인 코드

#include <string>
#include <vector>
using namespace std;
/*

칸 회전 -> 즉, 맨 앞을 맨 뒤로 보내고 문자열 체크
doubleS -> [](){}[](){}
*/
int solution(string s) {
    int answer = 0;
    string doubleS = s+s;
    
    int n1 = (int)s.size()-1;
    int n2 = n1 *2;
    
    int l = 0;
    int r = n1;
    while(r<=n2)
    {
        // 소괄호 중괄호 대괄호
        int s = 0;
        int m = 0;
        int b = 0;
        bool front = true;
        for(int i =l; i<=r; i++)
        {
            // 맨 앞이 열린 괄호라면 그대로 종료
            if(doubleS[l] == ')' || doubleS[l] == ']' || doubleS[l] == '}') 
            {
                front = false;
                break;
            }
            
            /* 괄호 체크 */
            if(s==0 && doubleS[i] ==  '(') ++s;
            else if(s!=0&& doubleS[i] ==  ')') --s;
            else if (s==0&& doubleS[i] ==  ')') 
            {
                front = false;
                break;
            }
            
            if(m==0 && doubleS[i] ==  '{') ++m;
            else if(m!=0&& doubleS[i] ==  '}') --m;
            else if (m==0&& doubleS[i] ==  '}') 
            {
                front = false;
                break;
            }
            
            if(b==0 && doubleS[i] ==  '[') ++b;
            else if(b!=0&& doubleS[i] ==  ']') --b;
            else if (b==0&& doubleS[i] ==  ']') 
            {
                front = false;
                break;
            }
        }
        
        if(front && s ==0 && m ==0 && b ==0) ++answer;
        
        ++l;
        ++r;
    }
    
    return answer;
}

 

---

맞는 풀이

1. 슬라이딩 윈도우 l,r 은 맞음

2. Stack으로 접근

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

using namespace std;

bool isValid(const string& s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }

    return st.empty();
}

int solution(string s) {
    int answer = 0;
    int n = s.size();
    string doubleS = s + s;

    for (int start = 0; start < n; ++start) {
        string sub = doubleS.substr(start, n); // 길이 n짜리 구간
        if (isValid(sub)) ++answer;
    }

    return answer;
}