안녕하세요 욱 입니다[...]
편하게 쉬운문제 에디토리얼쓰기
문제 설명
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^4 가지의 상태공간이 존재하는데 600^4 는 좀 큰 수이므로 배열로 counting 하기에는 부적절한데,
잘 생각해보면 substring 의 개수는 기껏해야 60000개를 넘지 않으므로 map 등의 자료구조를 쓰면 되겠죠. 혹은 해쉬를 써도 되는데, 아무래도 해쉬보다는 map이 제일 편할 듯 싶습니다. map 연산 당 시간복잡도는 O(lgn) 이하이므로, 전체 시간복잡도는 O(n lgn)이 됩니다 :)
map에서 key가 되는 부분은 int 값을 4개 가지는 구조체가 될 수도 있는데, 저 같은 경우는 600^4 가 64bit integer 로 표현되므로 가능한 모든 스트링에 (A의 개수)*600^3 + (C의 개수)*600^2 + (G의 개수)*600 + (T의 개수) 라는 값을 대응시켜서 풀었네요.
사실 방법이 그렇게 어려운 문제가 아니기 때문에, 설명보다도 코드를 보시는 것도 좋을 듯 합니다 :D

#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;
}