[Codeforces 950C] Zebras

[Codeforces 950C] Zebras - 1600

문제 설명 : 

문제에서 'zebra'라는 특정 문자열을 정의해주는데 이 문자열은 시작과 끝은 반드시 '0'이어야하고, 0과 1이 번갈아가면서 나타나야한다. 그래서 0과 1로만 이루어진 문자열이 주어졌을 때 이 문자열을 적당히 분할하여 모든 substring을 'zebra' 문자열의 조건을 만족시킬 수 있는지 찾는 문제이다.

풀이 : 

0 뒤에는 가장 가까운 1을 찾고, 1 뒤에는 가장 가까운 0을 찾는 방식으로 풀면 된다. 이때 substring의 시작과 끝은 반드시 0이어야하므로, 1로만 시작되거나 1로 끝나는 substring이 발견되었을 때는 불가능처리를 한다. 처음에 이 풀이에 대한 구현을 현재 문자에대한 다음(find)문자를 문자열 끝까지 쭉 훑어서 존재하는지 확인하는 방식으로 짰는데, 이 경우에 000...000 같은 문자열의 경우는 처음 0을 발견하고 1을 찾기위해서 문자열 끝까지 계속 살펴야하므로 시간복잡도가 O(N^2)이다. N이 최대 20만이므로 시간을 더 줄여야만 했다. 

그래서 생각한 방법은 0과 1의 위치(인덱스)를 따로 set에다가 저장해놓고 find문자를 찾을 때는 현재 문자의 인덱스보다 큰 인덱스 중에서 가장 작은 값을 구해야 하므로 set의 lower_bound연산을 이용했다. 그래서 문자를 찾을 때마다 set에서 해당 값은 삭제시킴으로써 set0의 원소가 빌 때까지 실행하면 된다.

주의할 점 : 

예외처리로 고려해야 할 부분이 많다. 앞서 말했다시피 substring이 1로 시작하거나 끝나서는 안되므로 이를 감지하는 조건문을 넣어주고 0의 원소는 0개인데 1의 원소가 아직 남아있는 경우에도 따로 처리를 해주어야 한다.

배운 점 : 

set의 erase와 lower_bound연산의 활용이 중요한 문제였다.

set.erase(원소) : 해당 원소의 값을 삭제, 혹은 set.erase(iterator) : 현재 iterator가 가리키고 있는 원소 삭제

코드 : 

#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;
typedef pair<int,int> Cord;
#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;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 200009;
 
char str[SIZE]={0};
int check[SIZE]={0};
vector<vector<int>> ans;
set<int> s0,s1;
 
int main(){
    scanf("%s",str+1);
    int len=strlen(str+1);
 
    for(int i=1 ; i<=len ; i++){
        if(str[i]=='0') s0.insert(i);
        else s1.insert(i);
    }
 
    int possible=1;
    while(!s0.empty()){
        vector<int> tmp;
        char find='0';
        int last=0;
        
        while(1){
            if(s0.size()==0 && s1.size()==0) break;
            if(s0.size()==0 && s1.size()>0){possible=-1; break;}
 
            if(find=='0'){
                auto cur=s0.lower_bound(last);
                if(cur==s0.end()) break;
                tmp.push_back(*cur);
                last=*cur;
                find='1';
                s0.erase(cur);
            }
            else if(find=='1'){
                auto cur=s1.lower_bound(last);
                if(cur==s1.end()) break;
                tmp.push_back(*cur);
                last=*cur;
                find='0';
                s1.erase(cur);
            }
        }
 
        if(str[tmp.back()]=='1') possible=-1;
        else if(tmp.size()>0) ans.push_back(tmp);
    }
    if(!s0.empty() || !s1.empty()) possible=-1;
    if(possible==-1){printf("-1\n"); return 0;}
 
    printf("%d\n",ans.size());
    for(int i=0 ; i<ans.size() ; i++){
        printf("%d ",ans[i].size());
        showAll(ans[i],SPACE);
        printf("\n");
    }
    return 0;
}