[Hackerrank] - Maximum Palindromes

문제

주어진 문자 s 에서 l~r 까지의 index 중

최대 길이의 palindrome 의 개수에 mod 10^9 + 7 한 값을 구해라!

 

ex) S = madamimadam , l = 4, r = 7

S 의 l~r 문자열은 amim

해당 문자열에서 만들 수 있는 최대 길이의 palindrome 은

mam, mim 으로 총 2개! 여기서의 답은 2 가 됨

 

알고리즘 분류

Strings (medium)

 

사전지식

• 순열
• 모듈러 역원 ( 나눗셈 mod 연산)

순열은 우리가 알고 있는 nCr 공식

 

나머지 모듈러 연산

https://eine.tistory.com/entry/%EC%88%98%ED%95%99-%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-1#recentEntries

저 C 가 10^9 + 7 이 된다. 참고로 해당 수는 prime

이 때 B 의 역원을 구할 때 페르마의 소정리가 이용됨

 

풀이

 

※ 해커랭크 discussion 에 올려놓은 코드를 참고

 

사전 작업

 1. 각 문자열 길이에 따른 factorial 과 나머지 mod 를 미리 구해 놓는다.

 

 2. s 에서 각 길이까지 알파벳이 몇 개인지 구한다.

   해당 값은 2차원 배열인 cnt 에 저장한다.

int cnt[n+1][26];
   memset(cnt, 0, sizeof(cnt));
   for(int i=1;i<=n;i++)
    {
         cnt[i][s[i-1]-'a']++; 
    }
   for(int i=2;i<=n;i++)
   {
       for(int j=0;j<26;j++)
       {
           cnt[i][j]+=cnt[i-1][j];
       }
   }  

만약 s 가 a a b c d e 라면 cnt 는

	a	b	c	d	e	f ...
0	0
1	1	0
2	2	0
3	2	1
4	2	1	1
5	2	1	1	1
6	2	1	1	1	1

즉 cnt[i][] = s 의 i 번째까지의 각 알파벳 개수의 상태

 

l = 2, r = 4 일 때 ( a b c) 해당 문자열에서 a 의 개수를 구하고 싶다면

cnt[4][0] - cnt[1][0] = 1 가 된다.

 

max length 의 palindrome 개수

 

주어진 문자열에서 최대 palindrome 의 문자열을 이제 구해야 한다.

만약에 a a b b c 의 문자들이 있다면   

만들 수 있는 palindrome 의 경우는

a b c b a

b a c a b 가 된다.

여기서 홀수 개인 c는 있던 없던, 짝수개의 문자열인 a와 b 를 어떻게 나열 할 것인지만 보면 된다.

어차피 문자열의 반쪽만 나열하면, 나머지는 그 반대의 경우로 똑같이 나열해야 하니까

우리는 절반만 보면 된다!

 

즉 짝수개인 알파벳들을 절반으로 나누고, 그 문자열을 나열한 경우의 수가 

max legnth 의 palindrome 의 개수가 되는 것이다.

 

ex) a a a a a a b b b b c 가 있다면

a a a b b 를 나열한 가짓수를 계산하면 된다.

이는 5!/(3! x 2!)  이 된다.

 

만약 홀수 개인 문자가 2개 이상이라면?

ex)  a a b b c d

어차피 홀수 인 문자는 가운데 한개 밖에 못온다.

위의 경우는 가운데가 c 인 경우, d 인 경우 이렇게 2가지가 된다.

그러니까 그냥 해당 값에 홀수 개인 문자의 개수를 곱해주면 된다.

 

홀수개의 문자의 횟수가 1번이 아니라 3번, 5번 이렇게 나타난다면?

ex) a a b b c c c 

--> 아래 코드에서 설명하겠지만

c 2개가 짝수개에 들어가고 c 하나는 홀수개 하나 남는걸로 들어간다.

even += value/2;

 

 

즉 짝수개인 문자들만 구하고 이걸 mod 로 잘 나눠주면 된다.

 

for(int i=0;i<q;i++)
  {
      int l,r;
      cin>>l>>r;
     int even=0,odd=0;
      long long int den=1,num=0;//num=numerator,den=denominator
      for(int it=0;it<26;it++)
        {    int value=cnt[r][it]-cnt[l-1][it];
            if(value%2!=0)
             odd++;
            even+=value/2; //value 값이 홀수여도 짝수개의 문자들이 들어갈 수 있다
            den=(den*mmi[value/2])%M;//storing MMI values

        }
       
      num=fact[even];
       long long int ans=(num*den)%M;
       if(odd!=0)
       {
           ans=(ans*odd)%M;
       }
       cout<<ans<<endl;
  }
}    

 

 

전체 코드

( 출처 : https://www.hackerrank.com/challenges/maximum-palindromes/forum 의

AnKY_5501 씨 풀이.)

#include <bits/stdc++.h>
using namespace std;
# define M 1000000007

//여기서는 factorial 과 나머지 mod 연산 한 값을 미리 구해놓는다.
//this power function is uses to find modular multiplicative inverse
//as M is prime so MMI=x^(M-2);
 long long int power( long long int x,  long long int y, long long int m) 
{ 
    if (y == 0) 
        return 1; 
    long long int p = power(x, y / 2, m) % m; 
    p = (p * p) % m; 
  
    return (y % 2 == 0) ? p : (x * p) % m; 
} 



 int main()
{
  string s;
  cin>>s;
   int q;
  cin>>q;
  int n=s.length();
  

  // pre-computing factorial and modular multiplicative inverse
  long long int fact[n+1],mmi[n+1];
  fact[0]=1;
  mmi[0]=1;
  for(int i=1;i<=n;i++)
  { fact[i]=(fact[i-1]*i)%M;
    mmi[i]=power(fact[i],M-2,M);
  }
   
   
   //pre-computing frequency of alphabets using 1 based index as asked in question
    int cnt[n+1][26];
   memset(cnt, 0, sizeof(cnt));
   for(int i=1;i<=n;i++)
    {
         cnt[i][s[i-1]-'a']++; 
    }
   for(int i=2;i<=n;i++)
   {
       for(int j=0;j<26;j++)
       {
           cnt[i][j]+=cnt[i-1][j];
       }
   }  
  
  
  for(int i=0;i<q;i++)
  {
      int l,r;
      cin>>l>>r;
     int even=0,odd=0;
      long long int den=1,num=0;//num=numerator,den=denominator
      for(int it=0;it<26;it++)
        {    int value=cnt[r][it]-cnt[l-1][it];
            if(value%2!=0)
             odd++;
            even+=value/2;
            den=(den*mmi[value/2])%M;//storing MMI values

        }
       
      num=fact[even];
       long long int ans=(num*den)%M;
       if(odd!=0)
       {
           ans=(ans*odd)%M;
       }
       cout<<ans<<endl;
  }
}