문제 설명
문자열 s가 주어졌을 때, 주어진 모든 문자를 사용하여 만들 수 있는 서로 다른 회문(palindrome)의 개수를 구해야 합니다. 답이 매우 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다.
예를 들어 입력이 s = "xyzzy"라면 출력은 2가 됩니다. "zyxyz"와 "yzxzy"라는 두 가지 회문을 만들 수 있기 때문입니다.
풀이 접근 방법
회문의 핵심 성질은 문자들이 좌우 대칭으로 배치되어야 한다는 점입니다. 따라서 홀수 번 등장하는 문자는 최대 1개만 존재할 수 있으며, 존재한다면 정확히 문자열의 가운데에 위치해야 합니다. 이 성질을 활용하면 문제를 중복 원소가 있는 순열 계산으로 변환할 수 있습니다.
다음 단계로 문제를 해결할 수 있습니다.
m = 10^9 + 7 (결과를 나눌 모듈러 값)
char_freq := 문자열 s의 각 문자와 그 빈도수를 저장하는 맵 생성
odd := 0 (홀수 빈도를 가진 문자의 개수)
char_freq의 각 문자 k와 빈도 v에 대해 반복:
v mod 2가 1이면 odd를 1 증가
odd > 1이면 0을 반환 (회문을 만들 수 없음)
half_length := len(s) // 2 (문자열 길이의 절반)
res := half_length의 팩토리얼
dividor := 1
char_freq의 각 문자 k와 빈도 v에 대해 반복:
dividor := dividor * (v // 2)! (각 문자의 절반 개수에 대한 팩토리얼을 누적 곱셈)
(res // dividor) mod m 반환
이 방법이 작동하는 이유는 다음과 같습니다. 회문의 왼쪽 절반이 결정되면 오른쪽 절반은 자동으로 대칭되어 결정됩니다. 따라서 전체 길이의 절반에 대한 순열 수를 계산하되, 같은 문자끼리의 중복을 제거하기 위해 각 문자 빈도의 절반에 대한 팩토리얼로 나누어 줍니다. 이는 중복 원소를 포함한 순열 공식 n! / (n₁! × n₂! × … × nₖ!)과 동일한 원리입니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
from math import factorial
class Solution:
def solve(self, s):
m = (10**9+7)
char_freq = {}
for c in s:
char_freq[c] = char_freq.get(c, 0) + 1
odd = 0
for k, v in char_freq.items():
if v % 2 == 1:
odd += 1
if odd > 1:
return 0
half_length = len(s)//2
res = factorial(half_length)
dividor = 1
for k, v in char_freq.items():
dividor *= factorial(v//2)
return (res//dividor) % m
ob = Solution()
print(ob.solve("xyzzy"))
입력
"xyzzy"
출력
2
복잡도 분석
시간 복잡도: O(n) — n은 문자열의 길이입니다. 문자 빈도 계산과 팩토리얼 연산에 선형 시간이 소요됩니다.
공간 복잡도: O(k) — k는 서로 다른 문자의 개수입니다.