'Programming Problems/Strings'에 해당되는 글 12건

 [ 1 ]  [ 2 ] 
Programming Problems/Strings

string transform

한번에 같은 문자들을 전부 다른 문자로 바꾸는 동작을 할 수 있다.

이 동작으로 한 문자열에서 다른 문자열로 바꾸는 것이 가능한지 확인하시오.


꼬리문제 : 바꾸는 것이 가능한 문자열이라 할때, 중간에 버퍼를 삽입해야만 바꿀 수 있는 경우가 있다. 이런 경우인지 확인해 보시오.

Programming Problems/Strings

a,b,c의 조합으로 이루어진 문자열에서 aaa..bb...c.. 형태의 조합의 갯수

우선 DP로 풀이 가능할 듯.


int countnumber(string &s, int curr, int it){

if(curr==s.size()) return 0;

// go through

int ret = 0;

for(int i = curr ; i < s.size() ; i++){

if(s[i]==it+'a'){

ret += countnumber(s,i+1,it);

}else if(it!=2&&s[i]==it+'a'+1){

ret += countnumber(s,i+1,it+1);

}

}

return ret;

}


" 매 위치의 것을 포함하는 " 갯수를 세기 때문에, 섭문제의 합이 중복을 가지지 않는다 !!!

경우의 수를 DP로 셀때는 특히 현재 위치에서 아예 새로운 조합을 만들어내는지 잘 확인해야 한다.


시간 복잡도 : O(N^2)


다른 풀이법 ( 최적화된 선계산법 )


아예 "갯수를 세는" 과정 자체가 DP 가 하는건데, DP 자체를 선계산 해버릴 수 있다.


If current character is ‘a’, then there are following possibilities :
    a) Current character begins a new subsequence.
    b) Current character is part of aCount subsequences.
    c) Current character is not part of aCount subsequences.
    Therefore we do aCount = (1 + 2 * aCount);

    If current character is ‘b’, then there are following possibilities :
    a) Current character begins a new subsequence of b’s with aCount subsequences.
    b) Current character is part of bCount subsequences.
    c) Current character is not part of bCount subsequences.
    Therefore we do bCount = (aCount + 2 * bCount);

    If current character is ‘c’, then there are following possibilities :
    a) Current character begins a new subsequence of c’s with bCount subsequences.
    b) Current character is part of cCount subsequences.
    c) Current character is not part of cCount subsequences.
    Therefore we do cCount = (bCount + 2 * cCount);


O(N) 이란다. ㅋㅋ 그냥 경우의 수 계산을 손으로 한 풀이인듯

Programming Problems/Strings

ANAGRAM CHECKING

곱셈과 덧셈의 교환법칙에 의해 유일함이 담보된다.

아나그람을 체크할때, SUM,PRODUCT를 비교하면 O(M) 으로 만드는 시간만 걸리고 비교는 O(1) 이 걸린다.

만약 26개짜리 벡터를 비교하면 O(26) 이어서 조금 더 느리다.


시간복잡도는 같다.

Programming Problems/Strings

스크램블된 문자열을 dict를 이용해 해독해 보자.

hello to the world >> elhloothtedrowl이 된다.

이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다.


풀이 :


각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다.


vector<string> findoriginal(vector<string> & data, string & s){

// 벡터 키는 안되지만 된다고 가정. 비트 수준으로 숫자 조합을 모은 다음에 해시로 뭉개버리면 된다.

unordered_map<vector<int>,int> dict;

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

vector<int> counter(26,0);

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

counter[data[i][j]-'a']++;

}

dict.insert(pair<vector<int>,int>(counter,i));

}

return findoriginal(dict,s,curr);

}


vector<string> findoriginal(unordered_map<vector<int>,int> & dict, string & s, int curr){

if(curr==s.size()) return vector<string>():

// count map all words in dict


// 앞에서부터 순회하면서 카운트가 맞는 단어가 있으면 제시한다.

vector<string> ret = "";

vector<int> counter(26,0);

for(int i = curr; i < s.size() ; i++){

counter[s[i]-'a']++;

auto it = dict.find(counter);

if(it!=dict.end()){

vector<string> tmp = findoriginal(dict,s,i+1);

ret.insert(ret.end(),tmp.begin(),tmp.end()):

}

}

return ret;

}


재밌는건, dict에서 중복 사용이 가능하면 DP 가 가능해서 O(N^2) 알고리즘으로 캐핑이 가능하지만 만약 중복 사용이 불가능하면.. 디피가 안된다 .. ㅠㅠ 완전탐색이 되어버린다... 아닌가??

Programming Problems/Strings

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)

Programming Problems/Strings

string 앞에다가 최소한의 문자를 더해서 palindrome 만들기. 최소 갯수는?

일치하는 subfix와 postfix의 최대 길이를 물어보는건가?


bcacbc

aabbc


나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..

아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.

즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다.


abccd >> dccba abccd

bazcb

bczab >> 1개 겹치니까(뒤집은거의 앞에서부터) 4개 추가해서 bczabazcb로 만들 수 있다.


int findminadd(string s){

string t = s;

reverse(t.begin(),t.end());

int ret = 0;

while(s[ret]==t[ret]){

ret++;

}

return ret;

}


time complexity : O(N) ( 뒤집으니까 )

space complexity : O(N)

Programming Problems/Strings

두개의 스트링이 주어졌을 떄, 불연속적인 섭스트링의 갯수를 구해라

ex) "cat", "catapult"

>> "CATapult", "CatApulT", "CAtapulT"

답 : 3


솔루션 : 우선 바로 떠오르는 방법은 없으니 나이브에서 시작하자. DP로 비벼지는게 보인다 O(MN)으로.


int findall(string & s, string & t, int scurr, int tcurr){

if(tcurr==t.size()) return 1;

// go through starting from scurr

int ret = 0;

for(int i = scurr ; i<s.size() ; i++){

if(s[i]==t[tcurr]){

ret += findall(s,t,i+1,tcurr+1);

}

}

return ret;

}

캐싱을 적용하면 O(MN)으로 하드캐핑 된다. 그리고 내부 시간 복잡도는 최악의 경우 N에 비례하므로 결국 O(MN^2) 정도가 되지 않을까.


Programming Problems/Strings

k개의 종류로 이루어진 최대 길이 스트링 찾기 Q

ex ) aaaabbbb, k=2 >> aaaabbbb

asdfrttt, k=3 >> frttt



나이브 솔루션 : 긴 섭스트링부터 안에 있는 원소의 수가 맞는지 본다. O(N^3) 알고리즘.


해시 테이블을 이용한 트래킹.

헤드 테일을 곁들여서.


헤드를 늘려 가면서 맵에 원소의 수와 갯수를 체크한다.

갯수가 K 일때 길이를 확인한다.

K 보다 갯수가 많아지만 tail을 앞으로 보내면서 하나씩 뺀다.

갯수가 K일때 길이를 확인한다.

head를 K보다 갯수가 많아질때까지 계속 앞으로 보낸다.

헤드가 끝에 닿으면 계산하고 끝낸다.


O(N) 알고리즘 ..!!


Programming Problems/Strings

목표 string까지 하나씩 다른 dictionary의 시퀀스 구하기 Q

딕셔너리에 주어진 스트링 중에서 목표 string까지 하나씩 바꾼 시퀀스를 구해야 한다.

아래 내용물들이 딕셔너리에 주어진다고 가정할 떄,

CAT -> DOG


CAT -> COT -> DOT -> DOG 이다 ( 아무거나 구해도 된다 )


솔루션 :


우선, 두 시퀀스 중 서로 다른 문자는 무조껀 바꿔야 한다. 그 갯수를 N/k개라고 하면, 서로 다른 가능한 조합의 갯수는 2^N/k 개이다. 근데 그 조합들을 순서대로 짠다고 하면 결국 몇 경우가 없을 것 이 아니라.. 오히려 N/k개를 선택하는 조합의 갯수는..!! O(N/k!) 무려 이렇게 된다능.. 조합의 갯수보다 더 많다 ㅋㅋ..


근데 딕셔너리에 존재하는 것들의 갯수가 한정적이고, 한 경우만 찾으면 되니까,, 각 점에 대해 바꾸는 경우로 생각해 보면 DFS와 DP 로 비벼질 것 같기도 한데


bool find(string curr, string target, unordered_set<int> tochange, unordered_set<string> dict){

tochange의 모든 경우에 대해 조합을 시도한다.

curr[*it] = target[*it];

tochange.erase(it);

if(dict.find(curr)!=dict.end() && find(curr,target,tochange,dict)) return true;


return false;



시간복잡도가 최대 2^N으로 캐핑되기는 한다. curr의 상태 숫자 때문에 ..

그리고 딕셔너리가 별로 없으면 리커젼이 깊게 들어가지도 않을꺼고, DFS로 탐색하는거라 발견 시 그 이후는 리커젼이 안 들어가서 실제로는 좀 더 빠르긴 할듯..


( 딕셔너리를 조작하는 방법 )


딕셔너리를 순회하는건 좀 아닌 방법이긴 한데, 그 안에서 길이가 같은 것들을 전부 빼낸 다음에, 서로에 대해 방향 그래프를 그리고 최종 경로에 도달 가능한지 DFS로 알아보는 방법..


최악의 경우 원소의 숫자만 무한대 갯수.. ;ㅅ;


DP 로 비벼지는 경우가 있나?


;ㅅ;


우선 솔루션들을 보면 이게 리얼 레알 반박불까 빼박캔트 답인듯 !!! 너님은 채고임


Programming Problems/Strings

문자열의 ?, 0과 1로 치환한 모든 경우의 수 리턴하기

ex ) a?b?c >> a0b0c0 a0b0c1 ...


바로 코딩하겠읍니다..


void printallpermutations(string s, vector<string> & ret, int curr){

// general case

// go through until ? met

for(int i = curr; i < s.size() ; i++){

if(s[curr]=='?'){

s[curr]='0';

printallpermutations(s,ret,curr+1);

s[curr]='1';

printallpermutations(s,ret,curr+1);

return;

}

}

// base case

ret.push_back(s);

return;

}


순회는 "모든" 재귀함수들에 걸쳐 처음 : 1 * a1, 두번째 2* a2 ... 2^N * an 이고 a1+a2... + an = length 이다.

그리고 재귀함수의 총 호출횟수는 2^N+1 회..  , N = ?의 갯수, 대략 length에 비례한다고 생각해도 될 듯

대강 O(2^N) 정도가 아닐까?


space complexity 는 length * 2^N 이겠다.