본문 바로가기

Programming Problems/Strings

(12)
string transform 한번에 같은 문자들을 전부 다른 문자로 바꾸는 동작을 할 수 있다.이 동작으로 한 문자열에서 다른 문자열로 바꾸는 것이 가능한지 확인하시오. 꼬리문제 : 바꾸는 것이 가능한 문자열이라 할때, 중간에 버퍼를 삽입해야만 바꿀 수 있는 경우가 있다. 이런 경우인지 확인해 보시오.
a,b,c의 조합으로 이루어진 문자열에서 aaa..bb...c.. 형태의 조합의 갯수 우선 DP로 풀이 가능할 듯. int countnumber(string &s, int curr, int it){if(curr==s.size()) return 0;// go throughint 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..
ANAGRAM CHECKING 곱셈과 덧셈의 교환법칙에 의해 유일함이 담보된다.아나그람을 체크할때, SUM,PRODUCT를 비교하면 O(M) 으로 만드는 시간만 걸리고 비교는 O(1) 이 걸린다.만약 26개짜리 벡터를 비교하면 O(26) 이어서 조금 더 느리다. 시간복잡도는 같다.
스크램블된 문자열을 dict를 이용해 해독해 보자. hello to the world >> elhloothtedrowl이 된다.이때 이걸 해독할 수 있을까? 단어는 전부 딕셔너리에 들어있다. 풀이 : 각 단어를 카운팅한다. 이제 문자열을 앞에서부터 순회하면서 카운트가 맞는 단어가 있는 경우에 찾아서 그걸 자르고, 빼고( 중복이 가능한가 ?? 여기서는 유일한 조합만 있다고 하자 ) 남은 문자열에서 같은 작업을 재귀해 준다. vector findoriginal(vector & data, string & s){// 벡터 키는 안되지만 된다고 가정. 비트 수준으로 숫자 조합을 모은 다음에 해시로 뭉개버리면 된다.unordered_map dict;for(int i = 0 ; i < data.size() ; i++){vector counter(26,0);for(in..
n strings를 subsequence로 가지는 가장 lexiographically small한 string 그래프 문제 같은데..?? abcdedrive a > b > c > d > ed > r > i > v > e 이런식으로 directed graph가 되고 근데 DAG는 아니라서 topological sort는 안될꺼같은데,이 방법은 아닌거같다. 중복되는 문자들이 계속 나올 수 있는데 구현이 쉽지 않고 큰 의미를 찾기 어렵다. 완탐 , DP?최적화?어 이거 그거 될꺼같은데 트라이 만들기 비슷하게 아니면 앞에서부터 하나씩 꺼내기 bcdeppleirplaneoytdrive abca 맨 앞의 원소들 중 가장 작은 원소부터 꺼낸다. 중복이 있으면 전부 같이 꺼낸다. multimap을 쓰는게 제일 간단하고 효율적이겠다. logN * M(길이) 가 복잡도다 !! 엄청난 알고리즘.. string makesmallest..
string 앞에다가 최소한의 문자를 더해서 palindrome 만들기. 최소 갯수는? 일치하는 subfix와 postfix의 최대 길이를 물어보는건가? bcacbcaabbc 나이브하게는 하나씩 더하면서 팰린드롬인지 확인.. ( 무생각 )..아아.. 왼쪽에서만 추가하니까.. 결국에는 오른쪽에 이상한게 있으면 전부 보충해줘야 한다.즉, 뒤집은 문자열을 하나 만들고(이게 상한이다) 겹치는 만큼 줄인다. abccd >> dccba abccdbazcbbczab >> 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(..
두개의 스트링이 주어졌을 떄, 불연속적인 섭스트링의 갯수를 구해라 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 scurrint ret = 0;for(int i = scurr ; i
k개의 종류로 이루어진 최대 길이 스트링 찾기 Q ex ) aaaabbbb, k=2 >> aaaabbbbasdfrttt, k=3 >> frttt 나이브 솔루션 : 긴 섭스트링부터 안에 있는 원소의 수가 맞는지 본다. O(N^3) 알고리즘. 해시 테이블을 이용한 트래킹.헤드 테일을 곁들여서. 헤드를 늘려 가면서 맵에 원소의 수와 갯수를 체크한다.갯수가 K 일때 길이를 확인한다.K 보다 갯수가 많아지만 tail을 앞으로 보내면서 하나씩 뺀다.갯수가 K일때 길이를 확인한다.head를 K보다 갯수가 많아질때까지 계속 앞으로 보낸다.헤드가 끝에 닿으면 계산하고 끝낸다. O(N) 알고리즘 ..!!