프로그래머스[Lv.2] - 괄호 회전하기

 

 

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

괄호 짝을 판별하는 문제이다.

유명한 문제이니 풀이법을 알고 있었다.

여는 괄호( '(', '[', '{' )가 나오면 vector(stack)을 이용하여 저장하고 넘어간 뒤, 닫는 괄호 ( ')', ']', '}' )가 나오면 vector의 마지막 요소가 현재 나온 닫는 괄호와 짝이 맞다면 올바른 괄호가 될 가능성이 있다.

괄호짝이 맞는 문자들은 더 이상 신경 쓰지 않아도 되기 때문에 vector에서 제거한다.

하지만, 짝이 맞지 않는다면 올바른 괄호가 될 수 없다.

이렇게 모든 요소를 살펴본 뒤, vector에 남은 요소가 없다면 올바른 괄호가 된다.
(올바른 괄호 짝이 맞으면 vector에서 제거하기 때문이다.)

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <deque>

using namespace std;

bool CheckCorrect(deque<char>& bracket)
{
    vector<char> temp;
    
    for(auto c: bracket)
    {
        if(c == '(' || c == '[' || c == '{')
        {
            temp.push_back(c);
        }
        else
        {
            if(temp.size() == 0) return false;
            
            if(c == ')')
            {
                if(temp.back() != '(') return false;
                else temp.pop_back();
            }
            
            if(c == ']')
            {
                if(temp.back() != '[') return false;
                else temp.pop_back();
            }
            
            if(c == '}')
            {
                if(temp.back() != '{') return false;
                else temp.pop_back();
            }
        }
    }
    
    if(temp.size() == 0) return true;
    return false;
}

int solution(string s) {
    int answer = 0;
    
    deque<char> bracket;
    for(auto c : s)
    {
        bracket.push_back(c);
    }
    
    //check
    for(int i = 0; i < bracket.size(); i++)
    {
        if(CheckCorrect(bracket)) answer++;
        
        //rotate
        char c = bracket.front();
        bracket.pop_front();
        
        bracket.push_back(c);
    }
    
    return answer;
}

---