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

문제 분석

이 문제는 주어진 문자열이 괄호로 이루어져 있을 때, 문자열을 왼쪽으로 여러 번 회전시켜 올바른 괄호 문자열이 되는 경우의 수를 구하는 문제입니다. 괄호 문자열은 소괄호 (), 중괄호 {}, 대괄호 []로 이루어져 있으며, 주어진 규칙에 따라 "올바른 괄호 문자열"로 정의됩니다.

올바른 문자열 규칙

• 기본 괄호 문자열: (), [], {}는 올바른 괄호 문자열입니다.
• 중첩된 괄호: 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 또한 올바른 괄호 문자열입니다.
• 연결된 괄호: 만약 A와 B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열입니다.

문제 풀이 접근 방법

• 해당 문제는 주어진 문자열을 왼쪽으로 한 칸 씩 회전하며 회전된 문자열이 올바른 문자열인지 검증해야 합니다.
• 회전을 한다 → 1바퀴를 돌면 모든 경우의 수를 검증 할 수 있다 → 문자열을 두배로 만들어 부분문자열을 사용
• 문자열 검증
  • 여는 괄호는 stack 에 넣습니다.
  • 닫는 괄호가 나왔을 때, stack 의 상단에 있는 괄호와 짝이 이루어 지는지 확인합니다.
  • 짝이 맞지 않다면 틀린 문자열입니다.
  • 문자열을 다 돌았을 때, stack 이 비어있지 않으면 틀린 문자열 입니다.

코드

#include <bits/stdc++.h>
using namespace std;

// 괄호 문자열이 올바른지 확인하는 함수
bool check(string s) {
    stack<char> st;

    // 문자열을 한 글자씩 확인
    for (int i = 0; i < s.length(); i++) {
        // 닫는 괄호일 경우
        if (s[i] == ']' || s[i] == ')' || s[i] == '}') {
            // 스택이 비어있다면 짝이 맞지 않음
            if (st.empty()) return false;
            // 닫는 괄호와 스택의 상단 괄호가 짝이 맞지 않으면 false
            if (s[i] == ']' && st.top() != '[') return false;
            if (s[i] == '}' && st.top() != '{') return false;
            if (s[i] == ')' && st.top() != '(') return false;
            // 짝이 맞으면 스택에서 제거
            st.pop();
        } else {
            // 여는 괄호는 스택에 추가
            st.push(s[i]);
        }
    }
    
    // 스택이 비어있어야 올바른 괄호 문자열
    return st.empty();
}

// 주어진 문자열을 회전하며 올바른 괄호 문자열을 찾는 함수
int solution(string s) {
    int answer = 0;
    string tmp = s + s; // 회전한 문자열을 쉽게 추출하기 위해 문자열을 두 배로 확장

    // s의 길이만큼 회전
    for (int i = 0; i < s.length(); i++) {
        // 회전된 문자열이 올바른 괄호 문자열이면 count 증가
        if (check(tmp.substr(i, s.length()))) answer++;
    }

    return answer;
}

int main() {
    cout << solution("}]()[{") << endl; // 출력 예: 2
}