프로그래머스 괄호 회전하기 (C++)

프로그래머스

"( )", "{ }", "[ ]" 소,중,대괄호로 이루어진 문자열을 입력받습니다. 해당 문자열안의 괄호들을 왼쪽으로 x번 만큼 회전 시켰을 때, 올바른 괄호가 되는 x가 몇개인지 찾아주세요.

"[][][]" => 올바음, "[({})]" => 올바름, "[((]))" => 안됨

 

 

풀이 방법

괄호 안에는 무조건 올바른 괄호가 들어가있어야 하기 때문에 stack을 이용하여 풀어야합니다.

 

if (c == '(' || c == '[' || c == '{')
    stk.push(c);

 

괄호를 여는 문자인 경우 stack에 추가해주고

 

char top = stk.top();
if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{'))
{
    stk.pop();
}

stack의 top과 짝이 맞다면 pop을 해줍니다.

 

"[(])"

만약 짝이 맞지 않는다면 위와 같은 상황이기에 올바르지 않다고 판단합니다.

또한 stack이 비어있다면 열려있는 괄호가 없는 상황에 닫는 괄호가 들어왔다는 뜻 이기에 올바르지 않다고 판단합니다.

 

while(cnt--)
{
    if (check(s))
        answer++;

    s = s.substr(1, s.size()-1) + s[0];
}

위 처럼 substr 함수를 이용하여 회전된 값을 구해준 후 올바른 괄호를 구성하는 문자열의 개수를 찾아주면 됩니다.

 

 

정답 코드

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <stack>

using namespace std;

bool check(string& str)
{
    stack<char> stk;
    for (char c : str)
    {
        if (c == '(' || c == '[' || c == '{')
            stk.push(c);

        else
        {
            if (stk.empty()) 
                return false;

            char top = stk.top();
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{'))
            {
                stk.pop(); 
            }
            
            else
                return false; // 짝이 맞지 않음
        }
    }

    return stk.empty();
}

int solution(string s) 
{
    int answer = 0;
    int cnt = s.size();
    
    while(cnt--)
    {
        if (check(s))
            answer++;
        
        s = s.substr(1, s.size()-1) + s[0];
    }
    
    return answer;
}