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

문제 설명

---

제한 사항 및 입출력 예제

---

알고리즘 개념

　괄호 문자의 규칙을 찾으면 되는 문제다. 내가 알고 있는 기존의 괄호 규칙은 총 3가지다.

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다
• 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다
• 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호쌍은 서로 교차하면 안 된다

 

　상당히 복잡해보이지만, 이 규칙을 자료 구조를 이용하여 한 번에 적용하여 해결할 수 있다. 바로 stack인데, 값을 push하기 전에 마지막 값과 비교하여 괄호 문자의 규칙을 만족하면 제거하거나 푸시하면 풀린다. 예를 들어 "()[]{}"와 "([]){}", "({)}[]"가 각각 stack에서 어떻게 처리되어야 할지 생각해보자.

 

각각의 case를 스택에 push, pop하는 과정

　어느정도 감이 오는가? 그렇다. 왼쪽 괄호 '(' , '{', '[' 가 온다면 stack에 push를 한다. 그후 오른쪽 괄호가 ')', '}', ']'가 온다면 stack의 top과 비교하여 괄호 문자 쌍이 완성되는 경우 stack에서 pop을 해주고, 그렇지 않은 경우엔 괄호 문자가 아니므로 break를 걸어주면 된다. 이렇게 LIFO의 구조를 가졌으므로 stack 자료 구조를 활용하는 것이다.

 

　이후 문자열을 회전하는 과정은 다양한데, 내가 채택한 것은 string class를 이용하는 것이다. 문자열의 맨 앞을 잘라내고, 그 문자를 맨 뒤에 붙이면 문자열이 마치 회전하는 것처럼 보일 것이다.

---

풀이

#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int cnt = s.length();
    int answer = 0;

    while (cnt--)
    {
        stack<int> st;
        bool check = true;

        for (char& ch : s)
        {
            if (st.empty() || ch == '(' || ch == '{' || ch == '[')
                st.push(ch);

            else if (st.top() == '(' && ch == ')')
                st.pop();

            else if (st.top() == '[' && ch == ']')
                st.pop();

            else if (st.top() == '{' && ch == '}')
                st.pop();

            else
            {
                check = false;
                break;
            }
        }

        if (check && st.empty())
            answer++;

        string first = s.substr(0, 1);
        string sub = s.substr(1, s.length() - 1);
        s = sub + first;
    }

    return answer;
}

 

※ 알고리즘

int solution(string s)
{
    int cnt = s.length();
    int answer = 0;

　반복 횟수를 지정하기 위해 int형 변수 cnt, 올바른 괄호 문자열의 개수를 반환하기 위한 int형 변수 answer를 초기화해준다.

 

    while (cnt--)
    {
        stack<int> st;
        bool check = true;

　문자열을 스택에 저장하기 위한 stack<int> st를 초기화 해주고, flag 변수 check도 초기화해준다. 이때 stack의 자료형을 char로 해도 무방하다.

 

        for (char& ch : s)
        {
            if (st.empty() || ch == '(' || ch == '{' || ch == '[')
                st.push(ch);

            else if (st.top() == '(' && ch == ')')
                st.pop();

            else if (st.top() == '[' && ch == ']')
                st.pop();

            else if (st.top() == '{' && ch == '}')
                st.pop();

            else
            {
                check = false;
                break;
            }
        }

　핵심인 for문이다. 문자열 s에서 문자를 하나씩 꺼내어 조건에 맞게 처리하는데, 왼쪽 문자일 경우 스택 st에 push해주고 괄호 문자가 완성되는 경우엔 스택 st에서 pop을 해준다. 만약 두 조건을 모두 만족하지 않는다면 괄호문자가 이나므로 check를 false로 해주고 break를 걸어주어 반복문을 탈출한다.

 

        if (check && st.empty())
            answer++;

　플래그 변수가 true이고 스택이 비어있으면 올바른 괄호 문자이므로 올바른 괄호 문자열의 개수 answer를 증가시켜준다.

 

        string first = s.substr(0, 1);
        string sub = s.substr(1, s.length() - 1);
        s = sub + first;
    }

    return answer;
}

　이제 문자열을 회전시킨다. 문자열의 첫번째를 substr() 함수를 이용해 잘라주고, 이 부분을 제외한 문자열sub를 만들어 둘을 합쳐주면 된다.

std::basic_string<charT, Traits, Allocator>::substr(size_type pos = 0, size_type count = npos)
문자열의 pos부터 count까지 잘라낸다.