Codeforces #1469A Regular Bracket Sequence

문제

https://codeforces.com/contest/1469/problem/A

걸린 시간

00 : 51 : 17

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

bool solve(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> stack;
    for(int i = 0; i < n; i++){
        if(s[i] == '('){
            stack.push_back(i);
        }
        else if(s[i] == ')'){
            if(!stack.empty()){
                stack.pop_back();
            }
            else{
                bool exist = false;
                for(int j = 0; j < i; j++){
                    if(s[j] == '?'){
                        exist = true;
                        s[j] = '(';
                        break;
                    }
                }
                if(!exist) return false;
            }
        }
    }
    int front = 0, back = 0;
    for(int i = 0; i < stack.front(); i++){
        if(s[i] == '?') front++;
    }
    for(int i = stack.front(); i < n; i++){
        if(s[i] == '?') back++;
    }
    if(!stack.empty()) back -= stack.size();
    if(back >= 0 && (back+front)%2 == 0) return true;
    else return false;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        if(solve()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

A 번 문제 치고는 솔루션이 빨리 떠오르질 않아서 조금 당황했던 문제다.

내 풀이는 물음표가 없다고 생각하고 스택을 이용한 괄호 검사를 진행하되 만약 닫는 괄호가 나왔을 경우 배열이 비어 있다면 닫는 괄호 앞에 물음표가 있는지 확인해 주었다. 만약 존재하지 않는다면 RBS 가 될 수 없으므로 NO 를 출력하고 존재한다면 여러 물음표 중 하나를 여는 괄호로 바꾸어 주었다. 괄호검사가 끝나면 스택이 비어있는지와, 물음표가 더 남아 있는지를 확인해야한다. 만약 스택이 비어있지 않다면 존재하는 모든 여는 괄호는 뒤에 오는 물음표와 짝을 맺어야 하므로 스택의 맨 아래 여는 괄호 위치로부터 뒤에 물음표가 몇개 있는지를 세고 여는 괄호 개수만큼 존재하는지를 확인한다. 만약 물음표의 개수가 부족하다면 NO 를 그렇지 않으면 남은 모든 물음표의 개수가 홀수개인지 짝수개인지를 센다. 짝수개일 경우에만 서로 짝을 이룰 수 있으므로 YES 를 그렇지 않으면 NO 를 출력한다.

constructive algorithm 문제라서 인지는 모르겠지만 써 놓고 보니 모두 필요한 설명인데도 너무 장황하게 느껴져서 과연 이게 맞을까 하는 의문이 든다. 다행히도 ac 를 받긴 했다.