[CF 828C] String Reconstruction

[CF 828C] String Reconstruction - 1700

문제 설명 : 

n개의 부분문자열(substring)과 이 부분문자열이 전체 문자열에서 등장하는 시작 위치가 주어진다. 이 부분문자열의 정보를 바탕으로 전체 문자열을 구성할 때, 사전순으로 가장 앞서도록 만드는 문제이다. (입력되는 정보는 모순되지 않는다)

풀이 : 

입력되는 정보는 모순되지 않으므로 단순하게 substring을 i번째 위치에 넣는다고 생각하면 된다. 하지만 naive하게 생각해서 k_i개의 위치에 대해서 substring의 모든 글자를 다 비교해보면 시간초과가 난다. 예를 들어 substring이 "aaa...aa"로 총 100만 글자이고, k_i=100만개 : {1,2,3,...100만}이라면 시간복잡도는 100만 * 100만이므로 터지게 된다. 따라서 이미 채워진 칸은 다음에 볼 때 제외시켜서 시간을 절약시켜야 한다. 이를 구현하기 위해서 set을 사용할 것이다. set에는 사용되지 않은 칸을 저장해 둘 것이다. 그래서 처음에 set에 1~200만을 집어넣는다. 그리고 substring의 위치가 제시되면, 그 위치의 lower_bound를 찾아서 글자수의 길이만큼 채우면 된다.

주의할 점 : 

-

배울 점 : 

set이나 map에서 lower_bound나 upper_bound를 찾을 때는 set.lower_bound(x) 로 사용하면 된다. 나는 처음에 lower_bound(set.begin(),set.end(),x)를 사용했는데 이 방식은 search하는데 O(N)만큼 걸린다고 한다.

그리고 set의 원소를 지우는 연산은 erase가 있으며 인자로 원소나 원소의 이터레이터를 넣어주면 된다. 반환 값은 지운 원소의 다음 원소의 이터레이터이다.

코드 :

#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); }
inline vector<int> int_seperation(int N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/*********************Contest Template***********************/
const int SIZE= 2000009;
 
set<int> unused;
char ans[SIZE]={0},str[1000009]={0};
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=1 ; i<=2000009 ; i++)
        unused.insert(i);
 
    while(n--){
        scanf("%s",str+1);
        int len=strlen(str+1);
        int m;  scanf("%d",&m);
 
        for(int i=1 ; i<=m ; i++){
            int cur;    scanf("%d",&cur);
            auto it=unused.lower_bound(cur);
 
            while(it!=unused.end()){
                if(*it>=cur+len) break;
                ans[*it]=str[*it-cur+1];
                it=unused.erase(it);
            } 
        }
    }
 
    int l;
    for(int i=2000005 ; i>=1 ; i--){
        if(ans[i]!=0) {l=i; break;}
    }
 
    for(int i=1 ; i<=l ; i++){
        if(ans[i]==0) printf("a");
        else printf("%c",ans[i]);
    }
 
    return 0;
}
/*
 
*/