BOJ - 4949 - 균형잡힌 세상

ggh·2022년 5월 11일

boj cpp ps stack

백준

목록 보기

12/112

BOJ - 4949 - 균형잡힌 세상

문제

4949번: 균형잡힌 세상

문제 개념

모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

즉. 올바른 VPS 괄호 여닫이여야만 한다.

구현

#include <iostream>
#include <vector>
using namespace std;

// 입력 : 공백이 있는 문자열 ... 오로지 '.'만이 문자열의 끝을 알림. 
// (), []만이 존재함. 
// ( or [ 둘이 ([)] 인 경우 어떻게 처리할까..? 
// ()[ || ([) 를 어캐 구분할까 

int main()
{
    vector<string> answer;    // output
    string str;
    answer.clear();
    while (1)
    {
        // 문자열 입력
        getline(cin, str);
        // stack init
        vector<char> VectorStack; 
        if(str[0] == '.') break;   
        // 판별 ()
        for(int i=0; i < str.size(); i++)   
        {   // 괄호를 입력 받으면 
			// 시작 괄호면 스택쌓기 
            if(str[i] == '(') VectorStack.push_back('(');
            if(str[i] == '[') VectorStack.push_back('[');
            if(str[i] == ')')
            {   // 스택이 비어있지 않고 스택의 최 상단에 시작괄호가 있다면 스택제거
                // () 인 경우 : 빈 스택으로 만듬 
                if(!VectorStack.empty() && *(VectorStack.end()-1) == '(') 
                    VectorStack.pop_back();
                // 빈 스택에 닫는괄호가 들어오면 no
                // ) 인 경우 : no 
                else{ answer.push_back("no"); break; }    
            }
            if(str[i] == ']')
            {   // 스택이 비어있지 않고 스택의 최 상단에 시작괄호가 있다면 스택제거
                // [] 인 경우 : 빈 스택으로 만듬 
                if(!VectorStack.empty() && *(VectorStack.end()-1) == '[') 
                    VectorStack.pop_back();
                // 빈 스택에 닫는괄호가 들어오면 no
                // ) 인 경우 : no  
                else{ answer.push_back("no"); break; } 
            }
            // 스택이 비어있고 .이 나오기 전까지 입력된 문자열을 확인했을 경우  
			if (VectorStack.empty() && i == str.length() - 2) 
                answer.push_back("yes"); 
			// 스택이 비어있지 않고 입력된 문자열을 확인했을 경우 
            else if (!VectorStack.empty() && i == str.length() - 2) 
                answer.push_back("no");
        }   
    }
    for(auto el : answer)
        cout << el << '\n'; 
}