[Algospot] 알고스팟 BRACKETS2 짝이 맞지 않는 괄호

출처: https://algospot.com/judge/problem/read/BRACKETS2

 Input 

3

()()

({[}])

({}[(){}])

 

 Output 

YES

NO

YES

스택 이용

- 열린 괄호인 경우 Stack에 push

- 닫힌 괄호인 경우 Stack의 마지막 원소가 무엇인지 확인합니다.

    - 비워져 있는 경우 유효성 X

    - 괄호 종류가 맞지 않은 경우 유효성 X

- 모든 Input Data가 끝난 후, Stack이 비워져 있지 않은 경우 유효성 X

    열린괄호가 잔재한 경우 ex) '(()'

 

---

#include <string>
#include <iostream>
#include <stack>
 
using namespace std;
 
bool solution(const string& str) {
    const string opened = "({["; //열리는 괄호 수준 ( : 0, { : 1, [ : 2
    const string closed = ")}]"; //닫히는 괄호 수준 ) : 0, } : 1, ] : 2
    
    stack<char> st;              
    for (const auto &c : str) {
        // 문자를 찾지 못한 경우 -1 반환
        // 열린 괄호인 경우 스택에 push
        if (opened.find(c) != -1) {
            st.push(c);
        }
        // 닫힌 괄호인 경우
        else {
            if (st.empty()) return false;
            
            // 괄호 종류가 서로 맞는지 확인
            if (opened.find(st.top()) != closed.find(c)) {
                return false;
            }
            // 두 조건을 만족한다면, 스택에서 열린 괄호 제거
            st.pop();
        }
        
    }
    // 스택이 정상적으로 비워져 있다면 성공
    // 그렇지 않은 경우 여는 괄호가 남은 Case
    return st.empty();
}
 
int main() {
    int C;
    cin >> C;
 
    while(C--){
        string str;
        cin >> str;
        if (solution(str)) cout << "YES" << endl;    
        else cout << "NO" << endl;
    }
}