[Codeforces 1153C] Serval and Parenthesis Sequence

[Codeforces 1153C] Serval and Parenthesis Sequence - 1600

문제 설명 : 

(,),? 로 이루어진 문자열이 주어진다. 이 중에서 ?로 채워진 칸은 임의로 ( 또는 ) 로 바꿀 수 있다. 이때 strict prefix(길이가 0이거나 n일 때는 제외하는 prefix)는 절대로 올바른 괄호열이 되어서는 안되게하면서, 전체 문자열은 반드시 올바른 괄호열이 되어야 한다. 이 두 조건은 만족하는 문자열을 구하는 문제이다.

풀이 : 

처음에는 엄청나게 오답을 꼬라박은 문제이다. 처음 풀이는 여는 괄호 '(' 을 +1, 닫는 괄호 ')'를 -1, 이것들의 누적합을 sum이라고 했을 때 sum이 1이나 2 사이에서만 움직이도록 통제하였다. 하지만 이 풀이는 " ???))) "같은 문자열을 처리할 수 없다(정답을 " ())))) " 라고 낼 것이다).

정답은 바로 전체 문자열에서 앞부분에는 여는 괄호를 최대한 많이 배정해서 sum을 높인 다음에, 반환점을 돈 후에는 다시 닫는 괄호만 배정해서 sum을 낮춘다. 그래서 최종 마지막 글자에 도달했을 때는 sum이 0이 되도록 하는 것이다. 이 방법으로 푼다면 처음 생각했던 풀이와 달리 중간에서 sum이 0이 되거나 끝에 0을 못 만드는 일을 피할 수 있다. 그래서 처음에 '?'의 개수를 세면서 최대로 배정할 수 있는 괄호의 개수가 몇 개인지 계산해야한다.

주의할 점 : 

예외처리를 해야할 부분이 꽤 있다. 일단 글자수의 길이가 반드시 짝수어야 한다. 홀수라면 올바른 괄호열 자체를 만들 수가 없기 때문이다. 그리고 괄호열을 다 만든 다음에 검증할 때도 마지막 글자에 도달하기 전에 0이 되어서도 안된다.

배운 점 : 

문자열 앞부분에는 (만 배정하고, 뒷부분에는 )만 배정함으로써 서로 충돌의 가능성을 없앤 방법이다.

코드 :

 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
/*********************Contest Template***********************/
const int SIZE= 300009;
char str[SIZE];
 
int main(){
    int n;    scanf("%d",&n);
    scanf("%s",str+1);
 
    exm=":(";
 
    if(n&1) exf();
    int sum=0,not_filled=0;
    for(int i=1 ; i<=n ; i++){
        if(str[i]=='?') not_filled++;
        else if(str[i]=='(') sum++;
        else sum--;
    }
    int op,cl;
    op=(not_filled-sum)/2,cl=not_filled-op;    
 
    for(int i=1 ; i<=n ; i++){
        if(str[i]=='?' && op>0){
            op--;
            str[i]='(';
        }
        else if(str[i]=='?')
            str[i]=')';
    }
 
    int check=0;
    for(int i=1 ; i<=n ; i++){
        check+=(str[i]=='(')?1:-1;
        if(check<0 ||(i<n && check==0)) exf();
    }
    if(check!=0) exf();
    else printf("%s",str+1);
    return 0;
}