n strings를 subsequence로 가지는 가장 lexiographically small한 string

그래프 문제 같은데..?? 

abcde

drive

a > b > c > d > e

d > r > i > v > e

이런식으로 directed graph가 되고 근데 DAG는 아니라서 topological sort는 안될꺼같은데,

이 방법은 아닌거같다. 중복되는 문자들이 계속 나올 수 있는데 구현이 쉽지 않고 큰 의미를 찾기 어렵다.

완탐 , DP?

최적화?

어 이거 그거 될꺼같은데 트라이 만들기 비슷하게 아니면 앞에서부터 하나씩 꺼내기

bcde

pple

irplane

oy

t

drive

abca

맨 앞의 원소들 중 가장 작은 원소부터 꺼낸다. 중복이 있으면 전부 같이 꺼낸다.

multimap을 쓰는게 제일 간단하고 효율적이겠다. logN * M(길이) 가 복잡도다 !! 엄청난 알고리즘..

string makesmallest(vector<string> & data){

// make buffer

multimap<char,int> buffer;

vector<int> curr(data.size(),0);

for(int i = 0 ; i < data.size() ; i++){

buffer.insert(pair<char,int>(data[i][0],i));

}

// make result string by appending smallest element

int flag = 0;

string ret = "":

while(buffer.size()!=0){

auto it = buffer.equal_range(*buffer.begin());

ret.push_back(*buffer.begin());

for(auto run = it->first; run!=it->second; run++){

// remove and increase index

if(curr[run->second]!=data.size()-1){

curr[run->second]++;

buffer.insert(pair<char,int>(data[run->second][curr[run->second]], run->second));

}

auto tmp = --run;

buffer.erase(run);

run = tmp;

}

}

return ret;

}

time complexity : O(MNlogN)

space complexity : O(N)