문제 76502. 괄호 회전하기

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

 

 

난이도 : Lv.2 

 

문제 요약 설명

올바른 괄호 문자열이란 다음과 같은 규칙을 만족해야합니다.

• 문자열에 존재하는 각 종류의 괄호는 열린 괄호와 닫힌 괄호의 개수가 같습니다. 
• 왼쪽부터 순차적으로 읽었을 때, 항상 같은 종류의 괄호는 열린 괄호의 개수 >= 닫힌 괄호의 개수이어야 합니다.
• 각 괄호 안에는 짝 지어진 괄호만 존재할 수 있습니다.

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

입력

• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s

입력 제한

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

입력 예제

// input
"[](){}"

// ans
3

 

풀이 방식

이 문제는 문자열 s를 왼쪽으로 0~s-1번 회전시킨 문자열을 각각 올바른 괄호 문자열인지 확인하고, 올바른 괄호 문자열의 개수 만큼 answer에 대입하면 되는 문제이다. 고려해야할 점은 0~s-1번 '회전한 문자열이 올바른 괄호 문자열인지 어떻게 판단할 것인가?' 이다. 이는 조건에 맞게 판단을 하면 되는데 이를 확인하는 방법은 어렵지 않다.

 

회전한 문자열이 올바른 괄호 문자열인지 어떻게 판단할 것인가?

올바른 괄호 문자열이 되려면 무엇보다 "각 괄호 안에는 짝 지어진 괄호만 존재할 수 있습니다."라는 조건에 주의해야한다. 해당 조건을 만족하기 위해 매번 이전 문자가 열린 괄호였을 때 절때 다른 종류의 괄호가 오면 안된다. 예를 들어, '['다음에 소괄호 ')'나 중괄호 '}'가 오게되면 무조건 위 조건을 위반할 수 밖에 없기 때문이다. 따라서, 올바른 괄호 문자열인지 판단하려면 자료구조 stack을 사용하여 다음과 같이 검증한다.

• 문자열에 존재하는 각 종류의 괄호는 열린 괄호와 닫힌 괄호의 개수가 같습니다. 
  => 문자열을 전부 순회한 후에 stack이 비어있는 지 확인한다. 하나라도 있으면 false
• 왼쪽부터 순차적으로 읽었을 때, 항상 같은 종류의 괄호는 열린 괄호의 개수 >= 닫힌 괄호의 개수이어야 합니다.
  => 열린 괄호는 stack에 push, 닫힌 괄호는 pop을 한다. 만약 pop을 하려고 했을 때 stack이 비어있다면, 해당 조건을 위반한 것이므로 false로 처리한다.
• 각 괄호 안에는 짝 지어진 괄호만 존재할 수 있습니다.
  => 닫힌 괄호인 경우, 이전 문자가 해당 닫힌 괄호와 같은 종류의 열린 괄호인지를 확인한다. 그렇지 않다면, 해당 조건을 위반한 것으므로 false로 처리한다.

위의 모든 검증을 통과했다면 해당 문자열을 올바른 괄호 문자열임으로 true를 반환한다.

 

정답 코드 

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

using namespace std;

bool iscorrect(string s){
    stack<char> s1;
    map<char, char> m1 = {{']', '['}, {')', '('}, {'}', '{'}};
    
    for(char c : s){      
        // 스택이 비어있는 경우.
        if(s1.empty()){
            if(c == '[' || c == '(' || c == '{'){
                s1.push(c);
                continue;
            }
            else{
                return false;
            }
        }
        
        char prev_c = s1.top();
        if(c == ']' || c == ')' || c == '}'){
            if(m1[c] == prev_c){ s1.pop(); continue; }
            else { return false; }            
        }
        else { s1.push(c); }
        
        
    }
    
    return s1.empty();
}

int solution(string s) {
    int answer = 0;
       
    for(int i = 0; i < s.length(); i++){
        char c = s[0];
        s+= c;
        s.erase(s.begin(),s.begin()+1);
        
        //cout << s << '\n';
        if(iscorrect(s)){
            //cout << "sssssss" << '\n';
            answer++;
        }
    }
    return answer;
}