문제 소개
문자열 s와 숫자 k가 주어졌을 때, s에 포함된 모든 문자를 사용하여 k개의 회문(팰린드롬)을 만들 수 있는지 확인하는 문제입니다.
예를 들어 입력이 s = "amledavmel", k = 2라면 결과는 True입니다. 이 문자들을 조합하면 "level"과 "madam"이라는 두 개의 회문을 만들 수 있기 때문입니다.
핵심 아이디어
회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열입니다. 회문을 구성할 때 각 문자는 좌우 대칭으로 짝수 개씩 배치되며, 길이가 홀수인 회문이라면 가운데 위치에 단 하나의 문자만 홀수 개로 존재할 수 있습니다.
따라서 문자열의 문자들을 k개의 회문으로 나누려면, 홀수 번 등장하는 서로 다른 문자의 개수가 k 이하여야 합니다. 각 회문은 최대 한 개의 홀수 빈도 문자를 가운데에 배치해 흡수할 수 있기 때문입니다.
알고리즘 단계
- d := 각 고유 문자와 그 등장 빈도를 저장하는 맵(Counter)을 생성합니다.
- cnt := 0으로 초기화합니다. (홀수 빈도를 가진 문자의 개수)
- d의 각 키에 대해 다음을 반복합니다:
- d[key]가 홀수이면 cnt를 1 증가시킵니다.
- cnt가 k보다 크면 False를 반환합니다.
- 반복이 끝나면 True를 반환합니다.
구현 예제
from collections import Counter class Solution: def solve(self, s, k): d = Counter(s) cnt = 0 for key in d: if d[key] & 1: cnt += 1 if cnt > k: return False return True ob = Solution() s = "amledavmel" k = 2 print(ob.solve(s, k))
입력
"amledavmel", 2
출력
True
동작 원리 설명
위 예제에서 "amledavmel"의 문자 빈도를 살펴보면 다음과 같습니다.
- a: 2회, m: 2회, l: 2회, e: 2회, d: 1회, v: 1회
홀수 빈도를 가진 문자는 d와 v, 총 2개입니다. k = 2이므로 홀수 빈도 문자의 개수(cnt = 2)가 k보다 크지 않아 True가 반환됩니다. 실제로 d와 v를 각각 "madam"과 "level"의 가운데에 배치하여 두 개의 회문을 완성할 수 있습니다.
시간 및 공간 복잡도
시간 복잡도: O(n) — 문자열을 한 번 순회하며 각 문자의 빈도를 계산하고, 서로 다른 문자의 개수만큼만 추가 확인을 수행합니다.
공간 복잡도: O(m) — m은 문자열 내 서로 다른 문자의 개수로, Counter가 이를 저장합니다.