백준 8933 [MCS]

출처 : www.acmicpc.net/problem/8933

 

문제

현대 분자 생물학에서 유전자 정보는 모두 DNA로 인코딩해서 나타낸다. 컴퓨터 과학에서는 DNA를 {A, G, T, C}로만 이루어진 길이가 아주 긴 문자열로 표현한다.

다른 것보다 많이 등장하는 DNA(부분문자열) 패턴을 찾는 일은 유전병 연구에서 매우 중요하다. 이 문제에서는 합성적으로 같은(compositionally equivalent) 부분문자열을 찾으려고 한다. 두 문자열 P, Q에서 등장하는 네 문자 {A, G, T, C}의 개수가 모두 동일할 때, P와 Q는 합성적으로 같은 문자열이라고 한다. 예를 들어, P="ATTATGC"와 Q="GTATCTA"는 P에서 등장하는 'A', G', 'C', 'T'의 개수가 Q와 같기 때문에, 두 문자열은 합성적으로 같다고 한다. "TTGCA"는 "TGCCA"와 합성적으로 같지 않다.

k-Major Composition Substring, 줄여서 k-MCS는 길이가 k인 부분 문자열중에서 가장 많이 등장하는 합성적으로 같은 부분문자열이다. 한 DNA의 k-MCS는 유일하지 않을 수도 있다. k-부분문자열은 길이가 k인 부분문자열을 나타낸다.

예를 들어, 길이가 14인 DNA 문자열 W="GCAGGAGCGCCAGG"에서 합성적으로 다른 3-부분문자열은 GCA, CAG, GGa, GAG, ..., CAG, AGG가 있다. "AGG"는 총 4번 (AGG, GGA, GAG, AGG) 등장하기 때문에, 이 문자열의 3-MCS가 된다. W에서 4번 보다 많이 등장하는 3-부분문자열은 없다.

DNA 문자열과 k이 주어졌을 때, k-MCS가 몇 번 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k(1 ≤ k ≤ 600)이고, 그 다음에 DNA 문자열 W가 주어진다. (10 ≤ |W| ≤ 60000)

출력

각 테스트 케이스 마다, 입력으로 주어진 W에서 k-MCS가 몇 번 등장하는지 출력한다.

예제 입력 1

3

3 GCAGGAGCGCCAGG

4 AGTCCTTAGAG

5 GGGAGGGGGGGTGGGGGGGGT

예제 출력 1

4

2

7

 

 

접근하기에 좀 많이 어려웠던 문제.

어떻게 접근해야할지 몰랐는데 map으로 풀어야하는 문제였다.

map은 이론만 배웠지 써본적이 없어서 오늘 처음 써봤다. (공부 좀 많이 하자...)

 

map<string, int> 이렇게 받으면 key를 string으로 value를 int로 받겠다는 뜻이다.

이 문제에서 map을 쓰는 이유는 다른 문자열을 구분하기 위해서!

즉, key에는 a,g,c,t의 개수를 숫자로 환산한 값을 넣고, value에는 같은 문자열의 개수를 넣어주면 된다.

Hash 함수에서 601을 곱한 이유는 k가 600이하이기 때문이다.

(hash라고 쓰면 stl에 hash함수가 존재하기 때문에 모호하다고 뜬다.)

 

map에 넣어줄 때는 map[key값]=value 이렇게 써주면 된다.

string 검사할 때 같은 문자열이 나오면 해당 index를 ++해주면 되고, 다른 문자열이면 그냥 1로 세팅해주면 된다.

(mp.end()면 해당 값을 못찾았다는 뜻)

 

출력은 map의 value를 출력해주면 되는데, 이건 iterator를 사용해서 쭉 검사해서 max값 출력해주면 된다.

(iterator도 너무 오랜만에 써봤다...)