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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

주어진 문자열을 0번~ s.size()-1번 회전했을 때 올바른 괄호의 개수를 세는 문제이다.

s의 입력 길이가 최대 1000이므로, 회전한 문자열 모두을 구해 올바른 괄호인지 확인하여도 TLE가 발생하지 않는다.

 

s를 i번 회전했을 때의 문자열은, s를 i번째 인덱스에서 끊고 앞 부분을 모두 문자열의 뒤로 이동시킨 것과 같다. 

i번 회전한 문자열을 구한 뒤, 해당 문자열이 올바른 괄호인지 확인하자.

 

문자열이 올바른 괄호인지 확인하는 방법은 다음과 같다.

먼저, 여는 괄호가 등장했을 때는 스택에 넣는다.

닫힌 괄호가 나왔을 때, 스택의 가장 최근 원소가 짝이 맞는 여는 괄호인지 확인하여 스택에서 삭제한다.

만약, 스택의 가장 최근 원소가 짝이 맞는 열린 괄호가 아니라면, 올바른 괄호가 아니다.

모든 문자를 순회하며 짝을 찾아 제거한 뒤에도 스택에 문자가 남아있는 경우에도 올바른 괄호가 아니다.

 

회전한 문자열 중에 올바른 괄호의 개수를 세어 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

char getPair(char x) {

    if (x == ')') return '(';
    if (x == ']') return '[';
    return '{';
}

bool check(string s) {

    stack<char> st;

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

int solution(string s) {

    int cnt = 0;
    for (int i=0; i<s.size(); i++) {
        string tmp = s.substr(i)+s.substr(0, i); //회전한 문자열
        if (check(tmp)) cnt++;
    }
    return cnt;
}