문제 이해하기
문자열 s가 주어졌을 때, 그 문자열의 아나그램(문자 재배열) 중 하나라도 회문(palindrome)을 이룰 수 있는지 확인해야 합니다.
예를 들어 입력이 s = "aarcrec"라고 가정해 보겠습니다. 이 문자열의 아나그램 중 하나인 "racecar"는 앞뒤가 같은 회문이므로 출력은 True가 됩니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 어떤 문자열이 회문이 되려면 문자들의 배치가 좌우 대칭을 이루어야 하며, 이는 각 문자의 등장 횟수에 다음과 같은 제약 조건이 있음을 의미합니다.
- 문자열의 길이가 짝수라면, 모든 문자가 반드시 짝수 번 나타나야 합니다.
- 문자열의 길이가 홀수라면, 정확히 하나의 문자만 홀수 번 나타날 수 있습니다(가운데 위치한 문자).
따라서 홀수 번 등장하는 문자의 개수가 1개 이하라면, 해당 문자열의 아나그램 중 하나는 반드시 회문이 될 수 있습니다. 문제를 해결하는 단계는 다음과 같습니다.
- freq := 모든 문자와 그 빈도수를 저장하는 맵 생성
- odd_count := 0으로 초기화
- freq의 모든 값 f에 대해 반복:
- f가 홀수라면 odd_count를 1 증가
- odd_count가 1보다 크면 False 반환
- 그렇지 않으면 True 반환
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
from collections import defaultdict
def solve(s):
freq = defaultdict(int)
for char in s:
freq[char] += 1
odd_count = 0
for f in freq.values():
if f % 2 == 1:
odd_count += 1
if odd_count > 1:
return False
return True
s = "aarcrec"
print(solve(s))입력
"aarcrec"
출력
True
동작 원리 살펴보기
입력 문자열 "aarcrec"의 각 문자 빈도수는 a: 2, r: 2, c: 2, e: 1입니다. 이중 홀수 번 등장하는 문자는 'e' 하나뿐이므로 odd_count는 1이 되고, 결과적으로 True가 반환됩니다. 실제로 이 문자들을 재배열하면 "racecar"라는 회문을 만들 수 있습니다.
시간 복잡도
이 알고리즘은 문자열을 한 번 순회하여 빈도수를 계산하고(O(n)), 다시 빈도 맵을 한 번 순회하므로(O(k), k는 서로 다른 문자의 개수) 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 문자 종류에 비례하여 O(k)입니다.