1218. 괄호 짝짓기 풀이

 

이번에 풀어볼 문제는 괄호 짝짓기이다. 

 

알고리즘 문제는 간단하게 풀이만 적도록 하려고 한다.

 

대충 이러한 문제이다.

 

 

* 이번 문제를 풀면서 중요하게 기억해야할 내용 *

1. stack 사용법과 다음 테스트 케이스를 위해 stack을 비워줘야함

 

2. 어떤식으로 탐색을 진행할 것인지 파악

-> 한쪽 형태의 모양을 스택에 우선 넣고나서 비교

 

3. 가장 중요한건 문제를 제대로 파악하는 것 

   -> 단순히 짝만 맞추는 것이 아니다. 문제에는 상세히 설명하지 않아서 안나왔지만

       가장 처음과 마지막은 괄호는 항상 '('  ')' 이런식으로 닫는 형태여야하며

       ')'  '(' 이렇게 는 자릴 바꾸면 한쌍이겠지만 문제에서는 한쌍으로 인정하지 않는다...

 

#include <iostream>
#include <stack>

using namespace std;

int main() {
    for(int a=1; a<=10; a++){
        stack<char>s;
        int count;
        string str;
        cin >> count;
        cin >> str;
        for(int i=0; i<str.length(); i++){
            if(str[i]=='{' || str[i]=='[' || str[i]=='(' || str[i]=='<')
                s.push(str[i]);
            else if(s.top()=='{' && str[i]=='}')
                s.pop();
            else if(s.top()=='[' && str[i]==']')
                s.pop();
            else if(s.top()=='(' && str[i]==')')
                s.pop();
            else if(s.top()=='<' && str[i]=='>')
                s.pop();
            else
                s.push(str[i]);
        }
        if(!s.empty())
            cout << "#" << a << " " << "0" << endl;
        else
            cout << "#" << a << " " << "1" << endl;
    }
    return 0;
}