#1 String Manipulation

마지막으로 푼 문제들 정리겸 포스팅.

 

1) String: Making Anagrams

Anagram의 기본적인 문제. 두 string을 서로 anagram 관계로 만드려면 알파벳을 모두 몇개 삭제해야되는지 출력하는 문제. 각 string의 alphabet counting후 다른 갯수를 리턴해주면 된다.

 

2) Alteranting Characters

하나의 string에서 문자열이 한번씩 반복되도록 하려면 문자열에서 문자를 몇개 삭제해야되는가? 의 문제

아주 간단한 반복문 문제. 첫 문자열을 저장해놓고, 반복문을 돌리면서 이전 문자열과 비교한다.

이전 문자열과 다르면 counting하지 않고, 이전 문자열과 같으면 counting한다.

 

3) Sherlock and valid string

valid string이란, 문자열에서 각 문자가 같은 "빈도"로 반복되는 걸 의미함. 단, 문자열에서 문자를 1번만 삭제해도 valid string조건을 만족한다면 valid하다. valid string을 만들 수 있는지를 return하는 문제다. 일단 문자열에서 알파벳의 빈도수를 체크한다. 예를들어서, abbcd라면 a:1 b:2 c:1 d:1 이다. 모든 문자가 1번씩만 반복이 되어야 하므로 b를 한번만 삭제하면 된다. 위 문자열에서 빈도수는 (1,2,1,1)이라고 할 수 있다. 이 벡터를 sorting을 시킨다. 그럼 (2,1,1,1)이 되겠지. for문을 돌면서 max값을 넣고, 다음 값을 체크한다. max값이랑 같으면 skip. 이제 max값은 삭제할 수 있는 가능성이 사라졌다. 높은 빈도수를 가진게 2번 나왔으니께. 그럼 나머지를 돌면서 max가 아닌 애를 한번만 삭제해도 되냐? 를 보면 된다. max값을 넣고 for문 처음에 다른게 나왔을때도 같다. 만약 다른게 나오면 그 다른값으로 갱신시켜준후에 삭제할수있는지 없는지를 본다.

 

4) Special String Again

만들 수 있는 special substring의 개수를 리턴하는 문제. special string은 중앙을 기점으로 좌우 대칭 문자라고 보면 되겠다. 일단 문자열을 쭉 훑어가면서 나타나는 빈도수를 consecutive하게 체크한다.

음.. 예를들어서, mnonopoo라면, m:1, n:2, o:4, p:1 이렇게 체크하는게 아니고, 문자 순서를 따라서 체크한다.

m:1 -> n:1 -> o:1 -> n:1 -> o:1 ->p:1 -> o:2 이렇게.

 

1개 이상의 같은 문자가 반복되는 substring의 개수는 n*(n+1)/2.

그 외에 좌우 대칭 문자를 구하기 위해서 for문을 돌면서 frequency가 1번인데 좌우 같은 문자가 있다면

좌우 frequency중에 작은값을 선택해서 counting한다.

 

5) Child String.

두개의 문자열중에 각각 어떤 문자들을 삭제했을 때 같은 string을 만들 수 있을 때 child String이라고 한다. child string의 maximum length를 구하는 문제이다. 이때 주의해야 할것은 순서가 유지가 되어야 한다.

 

즉

SHINCHAN / NOHARAA 이 두개가 주어졌을 때, 정답은 NHA = 3이다.

주의할 점은, ABCD와 ABDC가 있다 하면 CD의 순서가 바뀌어 있으므로 정답은 AD가 되는것이다. 즉. 문자열의 A->B->C->D 이 순서는 유지가 되어야 한다는 점이다.

 

어디서 많이 본 LCS문제이다. "최장부분공통수열" 주로 다이나믹 프로그래밍 예제에서 많이 쓴다.

1) 문자열이 같을 때 lcs(i,j) = lcs(i-1,j-1)+1

2) 문자열이 다를 때 lcs(i,j) = max(lcs(i-1,j),lcs(i,j-1))

 

최장부분공통수열만 생각해내면 풀이법은 어렵지 않다.

String은 정말 코딩테스트에서도 꼭 Easy~Medium 난이도 정도로 하나씩 출제되는 문제인데

정말 응용문제가 많다. 무궁무진한 string....