19장 짝이 맞지 않는 괄호 BRACKETS2

#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cassert>
#include<algorithm>
#include<queue>
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int cases;
    cin >> cases;
    assert(cases <= 100);
    while (cases--) {
        string s;
        stack<char> bracket;
        cin >> s;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                bracket.push(s[i]);continue;}
            if (!bracket.empty() && (bracket.top() == '('&&s[i] == ')')) {
                bracket.pop(); continue;}
            if (!bracket.empty() && (bracket.top() == '{'&&s[i] == '}')) {
                bracket.pop();continue;}
            if (!bracket.empty() && (bracket.top() == '['&&s[i] == ']')) {
                bracket.pop();continue;}
            if (bracket.empty() && (s[i] == ')' || s[i] == '}' || s[i] == ']')) { bracket.push(s[i]); break; }
        }
 
        if (bracket.empty()) cout << "YES" << endl;
        else cout << "NO" << endl;
        while (!bracket.empty()) bracket.pop();
    }
}

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

#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cassert>
#include<algorithm>
#include<queue>
using namespace std;
 
bool wellMatched(const string& formula) {
    //여는 괄호문자들과 닫는 괄호 문자들
    const string opening("({["), closing(")}]");
    //이미 열린 괄호들을 순서대로 담는 스택
    stack<char> openStack;
    for (int i = 0; i < formula.size(); i++) {
        if (opening.find(formula[i]) != -1)
            //여는 괄호라면 무조건 스택에 집어넣는다.
            openStack.push(formula[i]);
        else {
            //이 외의 경우 스택 맨 위의 문자와 맞춰보자.
            //스택이 비어 있는 경우에는 실패
            if (openStack.empty()) return false;
            //서로 짝이 맞지 않아도 실패
            if (opening.find(openStack.top()) != closing.find(formula[i]))
                return false;
            //짝을 맞춘 괄호는 스택에서 뺀다.
            openStack.pop();
        }
    }
    return openStack.empty();
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int cases;
    cin >> cases;
    assert(cases <= 100);
    while (cases--) {
        string s;
        stack<char> bracket;
        cin >> s;
        if (wellMatched(s)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

이 소스코드는 책에 나와있는 풀이이다.

이 문제에서 주의해야 될 점 두가지는

1. 전부 다 잘 처리하고 마지막에 열린 괄호가 남아 있는지 확인하는것.

2. 스택에서 여는 괄호를 꺼내려고 하는데 스택이 비어 있는 경우.  

내 코드에 비교해서 체계적이고 깔끔한 느낌이 드는 것 같다. find함수를 이용해서 푸는 방법도 염두에 둬야겠다.

두 풀이의 수행속도는 8ms로 동일하다.