알파벳 문자로 이루어진 문자열 s와 숫자 k가 주어졌을 때, 문자열 s에 포함된 문자만을 사용하여 만들 수 있는 길이 k의 회문(palindrome) 개수를 구하는 문제입니다. 각 문자는 필요하다면 여러 번 재사용할 수 있습니다.
예를 들어, s = "xy"이고 k = 4라고 가정해 보겠습니다. 이때 만들 수 있는 회문은 [xxxx, yyyy, xyyx, yxxy]의 4가지이므로 출력값은 4가 됩니다.
문제 해결 접근 방법
회문의 핵심 성질을 활용하면 이 문제를 매우 효율적으로 해결할 수 있습니다. 회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이므로, 길이 k인 회문은 다음과 같은 구조적 특징을 가집니다.
- 회문의 왼쪽 절반(첫 n개 문자)이 정해지면 오른쪽 절반은 좌우 대칭 원칙에 따라 자동으로 결정됩니다. 여기서 n은 k를 2로 나눈 몫(k // 2)입니다.
- k가 홀수인 경우에는 가운데 문자 하나가 추가로 필요하며, 이 문자 역시 s에 포함된 어떤 문자든 자유롭게 선택할 수 있습니다.
따라서 해결 절차는 다음과 같이 정리할 수 있습니다.
- n := k / 2의 몫 (정수 나눗셈)
- x := 문자열 s에 포함된 고유한(중복 없는) 문자의 개수
- x^(n + k mod 2) 값을 반환
직관적으로 설명하면, 왼쪽 절반의 각 위치마다 고유 문자 x개 중 하나를 선택할 수 있으므로 경우의 수는 x^n가지입니다. 여기에 k가 홀수일 때 가운데 문자 선택으로 인해 x배가 추가로 곱해지므로, 최종적으로 x^(n + k mod 2)가 전체 회문의 개수가 됩니다.
구현 예제
아래 파이썬 코드를 통해 더 쉽게 이해할 수 있습니다.
class Solution:
def solve(self, s, k):
n = k // 2
return len(set(s)) ** (n + k % 2)
s = "xy"
k = 4
ob = Solution()
print(ob.solve(s, k))
코드에서 set(s)를 사용하면 문자열에서 중복을 제거한 고유 문자들의 집합을 얻을 수 있으며, 그 길이가 곧 고유 문자의 개수 x가 됩니다.
입력
"xy", 4
출력
4
복잡도 분석
- 시간 복잡도: O(len(s)) — 문자열을 한 번 순회하여 고유 문자의 개수를 계산하는 데 드는 비용입니다.
- 공간 복잡도: O(x) — 고유 문자를 저장하기 위한 집합(set) 공간이 필요합니다.
이처럼 회문의 대칭성을 활용하면 모든 조합을 일일이 생성하지 않고도 단 한 번의 거듭제곱 계산만으로 정답을 빠르게 구할 수 있습니다.