Anagram

How many anagrams (including the initial word) does the given word have? by

pokorski

2000

Example

• For word = "abc", the output should be
  Anagrams(word) = 6.
• For word = "lol", the output should be
  Anagrams(word) = 3.

• [input] string word

  A word consisting of lowercase English letters.
  1 ≤ word.length ≤ 30.

• [output] integer

  The number of anagrams modulo 109 + 7.

problem link - https://codefights.com/challenge/28HC78S3MoJKX8LMX

주어진 문자의 Anagram의 총 갯수를 찾는 문제.

Anagram은 주어진 단어 안에 있는 알파벳들의 순서만 바꾼 또다른 단어를 의미한다 

예를 들어 'abcd'의 아나그램은 'bacd', 'cabd', 'dabc' 등등 해서 총 24개가 있다.

중복순열의 전형적인 예시이기에 구하는 공식은 매우 간단하다

문자의 총 길이에 팩토리얼을 취한 것(n!)에

중복되는 문자가 있다면 각자의 중복되는 수 만큼의 팩토리얼을 곱한 값들을 나눠준다. (r!, l!, m! 등등)

예를들어 'dead'라는 단어가 주어진다면

정답은 4! / 2! 해서 12인 것이다.

팩토리얼 계산식을 따로 구현,

문자열을 sort 시켜놓고 같은 문자들을 찾으면서

총 문자열의 길이의 팩토리얼에 중복되는 순열로 된 문자열의 팩토리얼의 곱을 나누면 된다.

제출했으나?! 역시 실패... 이 방법엔 크나큰 문제가 있다.

작은 규모의 문자열들은 완벽하게 계산해내나 조금만 문자열의 크기만 커져도

팩토리얼 계산이 들어가 있는 터라 int의 한계를 금방 벗어나버리는 것이다.

애초에 문제를 낼 때 이 문제를 해결하기 위해서

정답에다가 10의 9제곱 + 7의 나머지를 구한 값을 제출하라고 되어있다.

하지만 애초에 팩토리얼을 계산하는 과정 내에서 int의 한계를 훨씬 벗어나버려서 정답에다가 모듈을 바로 적용해도 틀린다.

어라, 이거 봐라? 하고 long long으로 자료형을 선언을 해도 그거마저 넘어서버린다..

테스트 케이스에 무려 30자가 넘는 문자열이 있다. 30팩토리얼 ㄷㄷ..

어떻게 해야 하는걸까?

팩토리얼을 한꺼번에 계산하는 방법은 안된다.

곱할때마다 바로바로 modular를 적용시켜가면서 정답의 범위를 int 내의 범위로 축소시켜야한다.