안녕하세요 욱 입니다[...]
편하게 쉬운문제 에디토리얼쓰기
문제 설명
ACGT로만 이루어진 길이가 k인 substring에 대하여 조성이 같으면(각 문자의 개수가 같으면) 같은 걸로 칠 때,
가장 많이 등장하는 것의 개수는 몇 개인가요?
풀이
간단한 스트링 문제로 쉽다는 생각을 갖고 덤벼보면 어렵지 않게 금방 해결할 수 있었던 문제입니다.
substring 에 길이 제한이 없다면 조금 어려울 수도 있겠지만 substring의 길이가 상수이므로, 가능한 substring 의 개수는 기껏해야 n-k+1 개입니다.
두 스트링을 같다고 판별하는 조건은 각 문자의 개수이므로, 우리는 스트링에서 각 문자가 나타난 횟수만을 기억하고 있으면 충분합니다!
그러니까 기본적으로 가능한 모든 substring들을 고려하여, 각 4가지 문자의 빈도수를 세고 이 빈도수에 따라 등장한 string의 수를 기억해 나가는 방식을 생각해 볼 수 있겠습니다.
O(n)개의 string들에 대해서 빈도를 세는 것을 각각 O(k)에 하면 O(nk)가 되지만,
substring 의 길이가 상수이기 때문에 앞에서부터 쭉 훑으면서 맨 뒤에 글자 하나를 붙이고 맨 앞의 글자 하나를 빼는 방식으로 하면 빈도를 계산하는 데에는 O(n)이면 충분합니다.
조금 더 자세히 적어보면, 처음에 k개 문자를 읽으면서 A C G T 각 문자가 몇번 등장했는지를 기억하고 있다가, i번째 문자 A[i] 를 넣고 i-k번째 문자 A[i-k] 를 빼면 될 것입니다. 넣고 뺀다는 거는 각 문자의 빈도수를 하나 증가시키거나 하나 감소시킨다는 거겠죠.
남은 것은 개수에 따라 스트링의 개수를 어떻게 기억하냐는 문제인데, k가 600 이하이므로 가능한 모든 경우는 600^4를 넘지 않습니다.
따라서 A의 개수, C의 개수, G의 개수, T의 개수에 따라 최대 600⁴ 가지의 상태공간이 존재하는데 600⁴ 는 좀 큰 수이므로 배열로 counting 하기에는 부적절한데,
잘 생각해보면 substring 의 개수는 기껏해야 60000개를 넘지 않으므로 map 등의 자료구조를 쓰면 되겠죠. 혹은 해쉬를 써도 되는데, 아무래도 해쉬보다는 map이 제일 편할 듯 싶습니다. map 연산 당 시간복잡도는 O(lgn) 이하이므로, 전체 시간복잡도는 O(n lgn)이 됩니다 :)
map에서 key가 되는 부분은 int 값을 4개 가지는 구조체가 될 수도 있는데, 저 같은 경우는 600⁴ 가 64bit integer 로 표현되므로 가능한 모든 스트링에 (A의 개수)*600³ + (C의 개수)*600² + (G의 개수)*600 + (T의 개수) 라는 값을 대응시켜서 풀었네요.
사실 방법이 그렇게 어려운 문제가 아니기 때문에, 설명보다도 코드를 보시는 것도 좋을 듯 합니다 :D
~~~ cpp

#include
#include
using namespace std;
int k;
char str[60006];
long long hash(long long a, long long b, long long c, long long d)
{
return a * 216000000 + b * 360000 + c * 600 + d;
}
int main()
{
int T;
scanf("%d", &T);
while(T-- > 0)
{
scanf("%d %s", &k, str);
int a, c, g, t, i;
a = c = g = t = 0;
map m;
// 처음 K개의 문자는 그냥 개수를 셈
for(i=0; i=k; ++i)
{
m[ hash(a,c,g,t) ] ++;
if(str[i] == 0) break;
if(str[i] == 'A') a++;
if(str[i] == 'C') c++;
if(str[i] == 'G') g++;
if(str[i] == 'T') t++;
if(str[i-k] == 'A') a--;
if(str[i-k] == 'C') c--;
if(str[i-k] == 'G') g--;
if(str[i-k] == 'T') t--;
}
int answer = 0;
for(map::iterator it = m.begin(); it != m.end(); ++it)
{
if(answer < it->second)
answer = it->second;
}
printf("%d\n", answer);
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/53777">원문보기</a>]</div>