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

문제 설명

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

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

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

 

제한 조건

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

 

입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

 

코드

#include <string>
#include <vector>

using namespace std;

bool is_open(char c)
{
    if (c == '(' || c == '{' || c == '[')
        return true;
    return false;
}

bool is_pair(char a, char b)
{
    if (a == '(' && b == ')')
        return true;
    if (a == '{' && b == '}')
        return true;
    if (a == '[' && b == ']')
        return true;
    return false;
}

bool is_right(string &s)
{
    vector<char> v;
    int i;
    
    for (i = 0; i < s.size(); i++)
    {
        if (is_open(s[i]))
            v.push_back(s[i]);
        else if (!v.empty() && is_pair(v.back(), s[i]))
            v.pop_back();
        else
            return false;
    }
    if (!v.empty())
        return false;
    return true;
}

int solution(string s) {
    int answer = 0;
    int x;
    string tmp;
    
    for (x = 0; x < s.size(); x++)
    {
        tmp = s.substr(x) + s.substr(0, x);
        if (is_right(tmp))
            answer++;
    }
    return answer;
}

 

스택을 활용하여 해결할 수 있는 문제이다. s의 부분 문자열로 왼쪽으로 x칸만큼 회전시킨 문자열 tmp를 구하고, 괄호가 열고 닫히는 순서가 올바른지 확인하여 answer 값을 더해주면 된다.

 

링크

코딩테스트 연습 - 괄호 회전하기

inbdni/Programmers