문자열 s가 주어졌을 때, s의 문자들을 재배열하여 만들 수 있는 순열(permutation) 중 하나라도 회문(palindrome)이 되는지 확인해야 합니다.
예를 들어 입력이 s = "admma"라고 가정해 보겠습니다. 이 문자열은 "madam"으로 재배열할 수 있고, "madam"은 앞에서 읽으나 뒤에서 읽으나 같은 회문이므로 결과는 True입니다.
풀이 접근 방식
실제로 모든 순열을 하나씩 만들어 확인할 필요는 없습니다. 회문의 기본 성질을 이용하면 문자 빈도 분석만으로 답을 구할 수 있습니다.
- 회문이 되려면 모든 문자가 짝수 번 등장해야 하고,
- 문자열 길이가 홀수인 경우에는 정확히 하나의 문자만 홀수 번 등장할 수 있습니다(가운데 자리에 배치됨).
따라서 다음 단계로 문제를 해결합니다.
collections.Counter를 사용해 문자열 s에 포함된 각 문자의 등장 횟수를 계산합니다.- 홀수 번 등장한 문자의 개수를 저장할 변수 count를 0으로 초기화합니다.
- 모든 문자 빈도를 순회하며 홀수 빈도를 확인합니다. 첫 번째 홀수 빈도라면 count를 1 증가시키고 계속 진행하고, 두 번째 홀수 빈도가 나타나면 즉시 False를 반환합니다.
- 순회를 마칠 때까지 두 번째 홀수 빈도가 없었다면 True를 반환합니다.
구현 예제
from collections import Counter
class Solution:
def solve(self, s):
c = Counter(s)
count = 0
for i in c.values():
if i % 2 != 0:
if count == 0:
count += 1
continue
return False
return True
ob = Solution()
s = "admma"
print(ob.solve(s))
입력
"admma"
출력
True
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 서로 다른 문자의 개수 k에 대해 O(k)입니다. 문자열의 길이에 비례해 선형적으로 동작하므로 매우 효율적입니다.
보너스: 파이썬다운 한 줄 풀이
같은 로직은 홀수 빈도의 개수를 세는 표현식으로 더 간결하게 작성할 수도 있습니다.
from collections import Counter
def solve(s):
return sum(v % 2 for v in Counter(s).values()) <= 1
핵심은 언제나 같습니다. 홀수 번 등장하는 문자가 최대 1개인지를 확인하면, 해당 문자열의 순열이 회문이 될 수 있는지 바로 판단할 수 있습니다.